Как создать декартовой продукт над произвольными группами чисел в Java?

Question

Скажем, у меня есть 2 группы чисел:

{1, 2, 3}, 
{4, 5} 

Я хотел бы создать алгоритм (в Java), который выдает следующие 6 комбинаций:

1,4 
1,5 
2,4 
2,5 
3,4 
3,5 

Там может быть произвольное число групп и произвольное количество членов в каждой группе. Таким образом, в приведенном выше примере есть две группы с первой группой, имеющей 3 члена, а вторая группа имеет 2 члена. Другим примером может служить следующее (3 группы, 3 члена в первых групп и 2 членов во второй и третьей групп):

{1, 2, 3}, 
{4, 5}, 
{6, 7} 

Какой бы дать следующие 12 комбинации:

1,4,6 
1,4,7 
1,5,6 
1,5,7 

2,4,6 
2,4,7 
2,5,6 
2,5,7 

3,4,6 
3,4,7 
3,5,6 
3,5,7 

Как можно сделать это в Java? Я пытаюсь использовать рекурсию, и я уже посмотрел на similar question, но я все еще не понимаю. Спасибо за помощь! (P.S. это не для домашнего задания)

Answer 1

Есть немного скучно, и решил дать ему шанс. Должно быть именно то, что вам нужно:

public static void main(String args[]) { 

    ArrayList<int[]> input = new ArrayList<int[]>(); 
    input.add(new int[] { 1, 2, 3 }); 
    input.add(new int[] { 4, 5 }); 
    input.add(new int[] { 6, 7 }); 

    combine(input, new int[input.size()], 0); 
} 

private static void combine(ArrayList<int[]> input, int[] current, int k) { 

    if(k == input.size()) { 
     for(int i = 0; i < k; i++) { 
      System.out.print(current[i] + " "); 
     } 
     System.out.println(); 
    } else {    
     for(int j = 0; j < input.get(k).length; j++) { 
      current[k] = input.get(k)[j]; 
      combine(input, current, k + 1); 
     }  
    } 
} 

Answer 2

Один из возможных подходов (не обязательно самый эффективный) может заключаться в том, чтобы использовать подход разделения и покорения. Сравнительно просто найти все перестановки двух групп (самый тупой путь просто вложен для циклов). Предположим, вы пишете функцию с именем permute и permute(A,B), где A (например, {(1), (2), (3)}) и B (например, {(4), (5)} являются группами чисел, и она возвращает вы все перестановки A & B как одна группа (например, {(1,4), (1,5), (2,4), (2,5), (3,4), (3,5) }).

Итак, если у вас есть N групп вместо 2, проще всего просто выделить небольшие части проблемы. Предположим, у вас есть группы A, B и C. Вместо того, чтобы беспокоиться о них все отдельно , вы можете думать об этом как о чем-то вроде:

permute(permute(A,B),C)

Найти все перестановки A и В первую очередь. После того как вы этот результат, найти все перестановки этого результата с С. И четыре группы A, B, C, D может выглядеть следующим образом:

permute(permute(permute(A,B),C),D)

И так далее. На каждом шаге по пути вы берете текущий результат перестановки и переставляете его следующей группой в списке групп, которые вы получили в качестве входных данных. Вы объединяете только две группы одновременно, поэтому алгоритм не должен меняться в зависимости от количества групп, которые вы получаете в качестве входных данных.

Когда вы делаете рекурсию, есть несколько основных вопросов, которые нужно ответить:

1. Вы можете рекурсивно разбить задачу на более мелкие, решаемые задачи? Я думаю, что приведенные выше примеры доказывают, что вы можете.

2. Что такое базовый корпус? Каково решение, которое заставит рекурсию остановиться и расслабиться? Обычно это должно быть что-то действительно простое, что ваша рекурсия может сработать. В этом случае это, вероятно, сводится к чему-то вроде permute(A,{}), где {} - пустой набор.

3. Что такое рекурсивный случай?Как вы отделите кусок проблемы и отнеситесь к меньшему подмножеству проблемы? Я думаю, что первоначальное объяснение дает вам один способ потенциально сделать это. Просто прерывайте одну группу за раз и переставляйте ее с вашим постоянно растущим результатом.

Есть, конечно, другие решения этой проблемы, это только первое, что появилось в моей голове. По мере того, как N становится все больше и больше, этот алгоритм будет становиться слишком медленным, поскольку он не очень эффективен.

Так что, даже если вы не используете это решение, я надеюсь, что он поможет вам на правильном пути!

Answer 3

Как насчет следующего псевдокода (без рекурсии)

// Create the initial result filled with the first set of numbers 
List result = new List() 
For each number in the first set 
    result.add(new List(number)) 

// Iterate over the following sets to permutate over 
For each remaining set S 
    List newResult = new List() 
    For each list L in result 
    For each number N in S 
     newResult.add(copy of L with N added) 
    result = newResult 

Answer 4

Если вы можете использовать библиотеки, Guava'sSets.cartesianProduct(List<Set<E>>) делает точно то, что вы ищете. (Раскрытие: я вношу свой вклад в Гуаву.)