항목 목록의 요소를 조합 집합으로 결합하는 가장 효율적인 방법은 무엇입니까?

Question

문자열을 예로 들어 List 목록을 제공한다고 가정 해 봅시다.

list 1: "a", "b", "c" 

list 2: "d", "e", "f" 

list 3: "1", "2", "3" 


results: (a, d, 1), (a, d, 2), ... (c, f, 3) 

내가 할 수있는 재귀 적 방법을 썼다

, (실제 사용 사례, 이것은 단지 모의 업입니다 문자열과 같은과 아무 상관이 없습니다) 그러나 나는 행복하지 않다 그것 때문에 던져 얻을 임시 세트를 많이 만듭니다 (예, 객체 생성이 Java에서 저렴하다는 것을 알고 있습니다. 일반적으로 C에서 malloc보다 더 적은 CPU 명령어 (소스 : Java Concurrency in Action, p241), eden GC는 저렴합니다. 유머 나 :).

void combine(List<List<String>> itemLists, List<Set<String>> combinations, Set<String> partial) { 
    if (itemLists == null || itemLists.isEmpty()) return; 
    List<String> items = itemLists.get(0); 
    for (String s : items) { 
     Set<String> tmpSet = new HashSet<>(partial); 
     tmpSet.add(s); 
     if (itemLists.size() == 0) //termination test 
      combinations.add(tmpSet); 
     else 
      combine(itemLists.subList(1, itemLists.size()), combinations, tmpSet); 
    } 
} 

그럼 어떻게할까요?

편집 : 명확히 말하면, 나는 순열을 만들고 싶지 않습니다. 나는 sizeof (리스트의리스트)가 큰 세트를 만들고 싶다.

Answer 1

목록 수가 가변적이며 해당 목록의 크기가 가변적이라고 가정하면 제공된 목록 각각에서 정확히 하나의 값을 포함하는 가능한 모든 집합의 목록이 필요합니다. 옳은?

다음과 같은 사항이 있습니까?

static List<Set<String>> combine(List<List<String>> itemLists) 
{ 
    // Calculate how many combinations we'll need to build 
    int remainingCombinations = itemLists.get(0).size(); 
    for(int i=1; i<itemLists.size(); i++) 
    { 
     remainingCombinations *= itemLists.get(i).size(); 
    } 

    List<Set<String>> allSets = new ArrayList<Set<String>>(); 

    // Generate this combination 
    for (;remainingCombinations > 0; remainingCombinations --) 
    { 
     Set<String> currentSet = new HashSet<String>(); 
     int positionInRow = remainingCombinations; 

     // Pick the required element from each list, and add it to the set. 
     for(int i=0; i<itemLists.size(); i++) 
     { 
      int sizeOfRow = itemLists.get(i).size(); 
      currentSet.add(itemLists.get(i).get(positionInRow % sizeOfRow)); 
      positionInRow /= sizeOfRow; 
     } 

     allSets.add(currentSet); 
    } 
    return allSets; 
} 

Answer 2

이 더 효율적입니다 :

: 작품을 계산 같은 방법 (각 "위치"당신의 목록 중 하나이며, 그 위치에 갈 수있는 각 "자리"목록의 요소)를 접근

List<Set<String>> combine(List<List<String>> input){ 

    final int n = input.size(); 
    int[] index = new int[n]; 

    List<Set<Sting>> result = new List<>(); 

    int position = 0; 
    while(position < n){ // "overflow" check 

     // Add set to result. 
     Set<String> set = new HashSet<>(); 
     for(int i=0; i<n; i++) 
      set.add(input.get(i).get(index[i])); 
     result.add(set); 

     // Now the "hard" part: increment the index array 
     position = 0; 
     while(position < n){ 

      if(index[ position ] < input.get(position).size()){ 
       index[position]++; 
       break; 
      } 
      else // carry 
       index[ position++ ] = 0; 
     } 
    } 
    return result; 
} 

(테스트하지 않았지만 몇 가지 버그가있을 수 있지만 주요 아이디어가 있습니다.) 일반적으로 재귀는 반복보다 느립니다.

Answer 3

"카티 션 제품"을 찾고 있습니다.

목록 대신 세트를 사용해도 괜찮 으면 Sets.cartesianProduct을 사용할 수 있습니다. 결과 목록에 대해 반복 할 때 할당 된 가비지가 여전히 있지만 다른 접근 방식만큼이나 중요하지는 않습니다.

(당신은 SO에서 코드 라인 수십 붙여 넣기보다 거기에 좀 더 자신감을 가질 수 있도록, 즉 공통 라이브러리 방법으로, 그것은 매우 철저하게 테스트 한 주.)

이 참고가되었습니다 request에 Lists.cartesianProduct도 있지만, 나는 아무도 그것에 대해 연구하고 있다고 생각하지 않습니다.