Jak stworzyć produkt kartezjański nad dowolnymi grupami liczb w Javie?

Question

Powiedzmy mam 2 grupy numerów:

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

Chciałbym stworzyć algorytm (w Javie), który wyprowadza 6 następujących kombinacji:

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

nie może być dowolna liczba grup i arbitralnej liczby członków w każdej grupie. Tak więc w powyższym przykładzie są 2 grupy, w których pierwsza grupa ma 3 członków, a druga grupa ma 2 członków. Innym przykładem jest następujący (3 grupami 3 członków w pierwszej grupie i 2 w drugiej i trzeciej grupie):

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

które dałoby 12 następujących kombinacji:

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 

Jak to zrobić to w Javie? Próbuję użyć rekurencji i już obejrzałem numer similar question, ale wciąż nie mogę się doczekać. Dzięki za pomoc! (P.S. to nie jest zadanie domowe)

Answer 1

trochę się nudzi i postanowił dać mu szansę. Powinny być dokładnie to, czego potrzebujesz:

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

Jednym z możliwych podejść (niekoniecznie najbardziej efektywnych) może być podejście polegające na podziale i podbiciu. Jest stosunkowo łatwo znaleźć wszystkie permutacje dwóch grup (najgłupszy sposób jest po prostu zagnieżdżony dla pętli). Załóżmy, że napisałeś funkcję o nazwie permute i ma ona postać permute(A,B), gdzie A (np. {(1), (2), (3)}) i B (np. {(4), (5)} są grupami cyfr i zwraca wszystkie permutacje A & B jako pojedynczej grupy (np. {(1,4), (1,5), (2,4), (2,5), (3,4), (3,5) }).

Więc kiedy masz N grup zamiast 2, najłatwiejszą rzeczą jest wyłapanie małych porcji problemu. Załóżmy, że masz grupy A, B i C. Zamiast martwić się o nie wszystkie osobno. można myśleć o tym, jak coś takiego:

permute(permute(A,B),C)

Znajdź wszystkie permutacje a i B pierwszy. Po uzyskaniu tego wyniku, znaleźć wszystkie permutacje tego wyniku z C i czterech grup A, B, C, D może wyglądać następująco:

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

i tak dalej. Na każdym kroku po drodze bierzecie aktualny wynik permutacji i permutujcie go z następną grupą na liście grup, które macie jako dane wejściowe. Łączymy tylko dwie grupy naraz, więc algorytm nie musi się zmieniać w zależności od liczby grup otrzymywanych jako dane wejściowe.

Kiedy robisz rekursji, istnieje kilka poważnych pytań trzeba odpowiedzieć:

1. można rekurencyjnie rozbić problemu na mniejsze, bardziej rozwiązywalnych problemów? Myślę, że powyższe przykłady dowodzą, że możesz.

2. Co to jest podstawowy przypadek? Jakie jest rozwiązanie, które spowoduje zatrzymanie i odreagowanie rekurencji? Zasadniczo powinno być coś naprawdę prostego, do czego rekurencja może doprowadzić. W tym przypadku prawdopodobnie sprowadza się do czegoś takiego jak permute(A,{}), gdzie {} jest pustym zestawem.

3. Co to jest przypadek rekurencyjny?W jaki sposób zerwiesz część problemu i powrócisz do mniejszego podzbioru problemu? Myślę, że wstępne wyjaśnienie daje ci jeden sposób potencjalnego robienia tego. Po prostu zerwij jedną grupę naraz i przesyłaj ją stale rosnącym wynikiem.

Z pewnością istnieją inne rozwiązania tego problemu, to tylko pierwsze, które pojawiły się w mojej głowie. Ponieważ N staje się coraz większy, algorytm ten staje się zbyt powolny, ponieważ nie jest zbyt wydajny.

Nawet jeśli nie korzystasz z tego rozwiązania, mam nadzieję, że doprowadzi Cię to na właściwą drogę!

Answer 3

Jak o następującym kodzie pseudo (w/o rekursji)

// 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

Jeśli można użyć biblioteki, Guava'sSets.cartesianProduct(List<Set<E>>) robi dokładnie czego szukasz. (Ujawnienie: wnoszę wkład do Guava.)