Java: декартово произведение списка списков
У меня есть проблема, которая на самом деле является вопросом общего программирования, но моя реализация находится на Java, поэтому я приведу свои примеры таким образом
У меня есть такой класс:
public class Foo {
LinkedHashMap<String, Vector<String>> dataStructure;
public Foo(LinkedHashMap<String, Vector<String>> dataStructure){
this.dataStructure = dataStructure;
}
public String[][] allUniqueCombinations(){
//this is what I need to do
}
}
Мне нужно сгенерировать вложенный массив из моей LinkedHashMap, который представляет каждую уникальную комбинацию всех значений в LHM. например, если мой LHM выглядит так (псевдокод, но я думаю, вы поняли..):
{"foo" => ["1","2","3"], "bar" => ["3","2"], "baz" => ["5","6","7"]};
тогда моя String[][] должна выглядеть так:
{
{"foo","bar","baz"},
{"1","3","5"},
{"1","2","5"},
{"1","3","6"},
{"1","2","6"},
{"1","3","7"},
{"1","2","7"},
{"2","3","5"},
{"2","2","5"},
{"2","3","6"},
{"2","2","6"},
{"2","3","7"},
{"2","2","7"},
{"3","3","5"},
{"3","2","5"},
{"3","3","6"},
{"3","2","6"},
{"3","3","7"},
{"3","2","7"},
}
Я думаю, это все, я сделал это вручную (очевидно), поэтому я мог пропустить набор, но я думаю, что это иллюстрирует то, что я пытаюсь сделать. Неважно, в каком порядке идет каждый набор, главное, чтобы присутствовали все уникальные комбинации. Также, чтобы было ясно, вы не знаете, сколько элементов находится в LHM или сколько элементов в каждом последующем векторе. Я нашел ответы, соответствующие случаю, когда вам нужна каждая уникальная комбинация всех элементов в одном массиве, но ничего, что точно соответствовало бы этому. Однако, если это точная копия вопроса, пожалуйста, поместите ссылку в ответ, и я закрою вопрос.
update — я изменил свои типы на строки, потому что мой реальный пример — это строки. Я пытался использовать целые числа, чтобы сделать пример более читабельным, но ответы, которые я получил до сих пор, плохо переводятся в строки.Итак, да, это числа, но в моем конкретном случае это будут строки, которые не будут иметь особого смысла ни для кого, кроме людей, которые используют это конкретное приложение. так что это просто абстракция.
1 ответ
Рекурсивное решение:
public <T> List<List<T>> cartesianProduct(int i, List<T>... a) {
if(i == a.length ) {
List<List<T>> result = new ArrayList<>();
result.add(new ArrayList());
return result;
}
List<List<T>> next = cartesianProduct(i+1, a);
List<List<T>> result = new ArrayList<>();
for(int j=0; j < a[i].size(); j++) {
for(int k=0; k < next.size(); k++) {
List<T> concat = new ArrayList();
concat.add(a[i].get(j));
concat.addAll(next.get(k));
result.add(concat);
}
}
return result;
}