비행 중에 조합법을 수행하는 방법

Question

저는 해결하기 어려운 몇 가지 제약이있는 매우 이상한 문제가 있습니다. 나는 목록 목록을 가지고 있으며 그 목록에있는 모든 항목의 조합을 원합니다. 각 항목에는 이름과 값이 있습니다.

홈페이지 목록 : 예를 들면 다음과 같습니다

• 목록 01 :
  • 항목 01 : 이름 : name01, 값 : value01
  • 항목 02 : 이름 : name02, 값 : value02
• 목록 02 :
  • 항목 01 : 이름 : name03, 값 : value03
  ,451,515,
• 목록 03 :
  • 항목 01 : 이름 : name04, 값 : value04
  • 항목 02 : 이름 : name05, 값 : value05

최종 결과는 같아야합니다 이 :

일부 목록 :

,
• 항목 01 : name01 : value01, name03 : value03, name04 : value04
• 항목 02 : name02 : value02, name03 : value03, name04 : value04
• 항목 03 : name03 : value03, name03 : value03, name04 : value04
• 항목 04 : name01 : value01, name03 : value03, name04 : value05
• 항목 05 : name02 : value02, name03 : value03, name04 : value05
• 항목 06 : name03 : value03, name03 : value03, name04 : value05

새 목록이 거의 포함되어 있습니다. 해시지도처럼 작동하는 항목

1. 나는 새 목록으로 수집하고 이러한 목록을 신속 매우 큰 성장할 수 있기를 혼합 할 수 없습니다 :

   제약을은 다음과 같습니다.

2. 나는 관측자와 비슷한 API를 사용하고 있으므로 관찰자에게 가능한 한 빨리 결과를 알려서 많은 메모리를 사용하지 않아야합니다.

즉,이 조합 생성기에는 각각 N 개의 항목을 포함 할 수있는 X 개의 목록이 제공 될 수 있으며 너무 많은 메모리를 사용하지 않고 조합을 생성해야합니다.

한 번에 5 개 이상의 목록을 사용할 것으로 예상하지는 않지만 가능한 한 코드 변경 사항을 복원 할 수 있도록 알고리즘을 만들고 싶습니다.

자바에서 문제를 해결하고 있지만 알고리즘은 번역 될 가능성이 높기 때문에 다른 언어에서도 똑같이 작동해야합니다.

의견이나 제안이 있으십니까?

미리 감사드립니다.

P. 나는 재귀가 잘 작동한다고 생각하지 않는다. 나는 while 루프와 몇몇 중첩 된 루프를 사용한다는 생각을 가지고 놀고 있지만 이것이 어떻게 작동해야 하는지를 생각하기가 정말로 어려워지고 있습니다.

Answer 1

그래서 이것은 데카르트 제품입니다.

2, 1 및 3 요소가있는 3 개의 목록을 가정하십시오. 0에서 5

void getCombiFor (int i, List <List <Integer>> li) 
{ 
    if (li.length > 0) 
    { 
     int idx = i % li.get (0).size();   
     System.out.print (li.get (0).get(idx));     
     getCombiFor (i - idx, li.remove (0)); 
    } 
    System.out.println(); 
} 
// pseudocodeline: 
List li = List (List ('a', 'b'), List ('c'), List ('d', 'e', 'f')) 
for (int i = 0; i < 6; ++i) 
{ 
    getCombiFor (i, li); 
} 

예 : (A * B를 * ... * 나는 추상적 인)

지금 당신이 6 개 숫자를 가지고 : 당신은 2 * 1 * 3 개 조합 = 6에 끝날 것

을

Lists = ((a,b), (c), (d,e,f)) 
acd 
bcd 
acf 
bcf 
ace 
bce 

Answer 2

주어진 목록 각각에 대해 하나씩 색인 배열을 만드는 방법은 어떻습니까? 현재 조합은 각 목록에서 차례로 get()을 수행하여 읽을 수 있습니다. 각 인덱스는 제로 것입니다 - 당신이 적용 할 다음 조합으로 이동합니다

index[0]++; 
if (index[0] >= list[0].size()) { 
    index[0] = 0; 
    index[1]++; 
    if (index[1] >= list[1].size()) { 
     ... 
    } 
} 

Answer 3

왜하지 (반복에의이 독자들에게 숙제로 남긴다 경우 중첩 된 켜기.) 실제로 해시 맵을 만들까요?

Map<String,Map<String,String>> mainMap = new HashMap<String,Map<String,String>>(); 

for(List l : lists) { 
    for(Data d : l) { 
     String item = d.item; 
     String name = d.name; 
     String value = d.value; 

     Map<String,String> itemMap = mainMap.get(item); 
     if(item == null) { 
      itemMap = new HashMap<String,String>(); 
      mainMap.put(item,itemMap); 
     } 
     itemMap.put(name,value); 
    } 
} 

나중에 특정 이름의 모든 값을 가져 오려면 어떤 항목이 필요합니까?

List<String> getValuesForName(String name) { 
    List<String> list = new LinkedList<String>(); 
    for(Map<String,String map : mainMap) { 
     String value = map.get(name); 
     if(value != null) list.add(value); 
    } 
    return list; 
} 

Answer 4

이 문제를 해결하기 위해 메모리를 사용할 필요가 없습니다. 전체 조합을 생성하지 않고 목록 수학의 N 번째 요소를 가져올 수 있습니다. 설명되어 있습니다 here