Как сделать комбинаторику на лету

Question

У меня очень странная проблема, которая имеет некоторые ограничения, которые затрудняют ее решение. У меня есть список списков, и я хочу сделать комбинации всех элементов в этих списках. Каждый элемент имеет имя и значение. Вот пример:

Основной список:

• Список 01:
  • Элемент 01: имя: имя01, значение: значение01
  • Элемент 02: имя: имя02, значение: значение02
• Список 02:
  • Элемент 01: имя: имя03, значение: значение03
• Список 03:
  • Элемент 01: имя: имя04, значение: значение04
  • Элемент 02: имя: имя05, значение: значение05

Конечный результат должен выглядеть следующим образом:

Некоторые списки:

• Элемент 01: имя01: значение01, имя03: значение03, имя04: значение04
• Элемент 02: имя02: значение02, имя03: значение03, имя04: значение04
• Элемент 03: имя03: значение03, имя03: значение03, имя04: значение04
• Элемент 04: имя01: значение01, имя03: значение03, имя04: значение05
• Элемент 05: имя02: значение02, имя03: значение03, имя04: значение05
• Элемент 06: имя03: значение03, имя03: значение03, имя04: значение05

Новый список в значительной степени содержит элементы, которые действуют как хэш-карта.

Ограничения следующие:

1. Я не могу собрать в новые списки и смешать их, потому что эти списки могут быстро стать довольно большими.
2. Я использую какой-то API-интерфейс, похожий на наблюдатель, поэтому мне нужно как можно скорее сообщить наблюдателю о результате, чтобы не использовать много памяти.

Другими словами, этот генератор комбинаций может быть снабжен X числом списков, каждый из которых может содержать N номеров, и я должен генерировать их комбинации, не используя слишком много памяти.

Я не рассчитываю работать с более чем 5 списками одновременно, но я хотел бы сделать алгоритм максимально устойчивым к изменениям кода.

Я решаю проблему в Java, но алгоритм должен работать одинаково и на других языках, потому что он может быть переведен.

У вас есть идеи, предложения?

Заранее спасибо.

P.S. Я не думаю, что рекурсия будет работать хорошо. Я согласен с идеей использования цикла while и некоторых вложенных циклов, но очень трудно представить, как это должно работать.

Answer 1

Итак, это декартово произведение, вы после?

Предположим, 3 списка, с 2, 1 и 3 элементами. Вы бы закончили 2 * 1 * 3 комбинаций = 6.

Теперь вы берете 6 цифр от 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);
}

Пример:

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

Answer 2

Вам не нужно использовать память для решения этой проблемы.Можно получить N-й элемент математики списка, не создавая целых комбинаций.Объясняется здесь

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

Как насчет создания массива индексов, по одному для каждого из заданных списков?Текущую комбинацию можно прочитать, выполнив get () для каждого списка по очереди.Каждый индекс будет равен нулю, а затем перейдет к следующей действующей комбинации

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

(превращение вложенного if в итерацию, оставленную в качестве упражнения для читателя.)