Znajdź wszystkie kombinacje w rekordzie rekurencyjnie

Question

Jestem całkowicie zagubiony w tej sprawie. Mogę to zrobić iteracyjnie, ale rekursja jest dla mnie nowością. Jeśli ja podano arraylist 1, 2, 3 w jej wnętrzu, całkowite możliwe kombinacje z powtórzeniami jest 27.

111, 112, 113, 121, 122, 123, itd ...

jak mogę znaleźć to rekursywnie? Chciałbym pokazać mój kod, ale nie jestem nawet blisko coraz koncepcję ...

Answer 1

Oto ciężko kodowane rozwiązanie, które po prostu wykonane w Pythonie, ale powinna wykazać zasadę:

def combinations(original,indexes): 
    indexes[2] = indexes[2] + 1 
    if(indexes[2] == 3): 
     indexes[1] = indexes[1] + 1 
     indexes[2] = 0 

    if(indexes[1] == 3): 
     indexes[0] = indexes[0] + 1 
     indexes[1] = 0 

    if(indexes[0] != 3): 
     print str(original[indexes[0]]) + str(original[indexes[1]]) \ 
      + str(original[indexes[2]]) 
     combinations(original, indexes) 


combinations([1,2,3],[0,0,0]) 

Zauważ, jak mam kombinacje funkcji(). Ta funkcja pobiera oryginalną tablicę jako parametr, a drugą tablicę do śledzenia indeksów.

Po wywołaniu funkcji, aby ją uruchomić, zainicjowałem tę tablicę indeksów do wszystkich 0.

Dla każdej funkcji w stosie należy zwiększyć indeksy w tablicy indeksów, aby uzyskać prawidłowe wyniki. Zauważ, że w moim rozwiązaniu używam trzech instrukcji if, jest to część zakodowana. Można to prawdopodobnie zrobić za pomocą pętli for.

Wreszcie, funkcja, która jest funkcją combination(), jest wywoływana ponownie wewnątrz siebie (rekurencja) ze zmodyfikowaną tablicą indeksów, dopóki nie zostanie spełniona klauzula końcowa (pierwszy indeks ma maksymalną wartość).

Ten fragment kodu powinien służyć jako przewodnik, jak widzę, że określili java

Answer 2

Oto metoda w Javie:

String combine(ArrayList<Integer> a, String b){ 
String c=""; 
    if(b.length()==a.size()){ 
    System.out.println(b); //found a combo 
    return ""; 
    } 
    //append characters to string b 
    for(int x=0;x<a.size();x++){ 
    c=b+((Integer)a.get(x)).intValue(); 
    c+=combine(a,c); 
    } 
    return c; 
} 

W każdej iteracji pętli, będzie dołączyć znak łańcucha b z tablicy array a wywołuje się rekurencyjnie. Gdy długość łańcucha b osiąga 3 (tj. Rozmiar listy tablic a), oznacza to, że generowane jest połączenie, które jest wyświetlane. Ta metoda jest uogólniona dla listy tablicowej o dowolnym rozmiarze.

Answer 3

Możesz użyć tej koncepcji i stworzyć własną funkcję rekursywną. korzystając z tego, że można uzyskać wszystkie możliwe kombinacje.

Answer 4

Jak o rozwiązanie, które nie obchodzi jeśli zmieniłeś rozmiar ArrayList?

public static void main(String args[]) { 
    ArrayList<Integer> ali = new ArrayList<>(); 
    ali.add(1); 
    ali.add(2); 
    ali.add(3); 

    System.out.println(combinations(ali).toString().replace("], [", "],\n [")); 
} 

To tylko mała pomoc na starcie.

public static List<List<Integer>> combinations(List<Integer> input) { 
    return step(input, input.size(), new ArrayList<>()); 
} 

Jest to metoda rekurencyjna,

public static List<List<Integer>> step(List<Integer> input, 
             int k, 
             List<List<Integer>> result) { 

    // We're done 
    if (k == 0) { 
     return result; 
    } 

    // Start with [[1], [2], [3]] in result 
    if (result.size() == 0) { 
     for (Integer i : input) { 
      ArrayList<Integer> subList = new ArrayList<>(); 
      subList.add(i); 
      result.add(subList); 
     } 

     // Around we go again. 
     return step(input, k - 1, result); 
    } 

    // Cross result with input. Taking us to 2 entries per sub list. Then 3. Then... 
    List<List<Integer>> newResult = new ArrayList<>(); 
    for (List<Integer> subList : result) { 
     for(Integer i : input) { 
      List<Integer> newSubList = new ArrayList<>(); 
      newSubList.addAll(subList); 
      newSubList.add(i); 
      newResult.add(newSubList); 
     } 
    } 

    // Around we go again. 
    return step(input, k - 1, newResult); 
} 

Wyjścia:

[[1, 1, 1], 
[1, 1, 2], 
[1, 1, 3], 
[1, 2, 1], 
[1, 2, 2], 
[1, 2, 3], 
[1, 3, 1], 
[1, 3, 2], 
[1, 3, 3], 
[2, 1, 1], 
[2, 1, 2], 
[2, 1, 3], 
[2, 2, 1], 
[2, 2, 2], 
[2, 2, 3], 
[2, 3, 1], 
[2, 3, 2], 
[2, 3, 3], 
[3, 1, 1], 
[3, 1, 2], 
[3, 1, 3], 
[3, 2, 1], 
[3, 2, 2], 
[3, 2, 3], 
[3, 3, 1], 
[3, 3, 2], 
[3, 3, 3]] 

Answer 5

Rozumiem walkę. Rozwiązywanie problemów rekurencyjnie często może być trudne, jeśli chodzi o śledzenie wszystkich połączeń i podejmowanie decyzji dotyczących poruszania się po problemie. Po chwili zastanowienia udało mi się rozwiązać ten problem, używając tablicy int do reprezentowania permutacji i ArrayList do przechowywania. Nie używano pętli ani sprawdzania powtórzeń.

Napisałem jedną łatwą do wywołania metodę getPermutations, która pozwala znaleźć wszystkie permutacje długości n z liczbami całkowitymi [1, n]. Ta metoda wywołuje rzeczywistą metodę rekursywną, która jest nieco bardziej złożona. Podczas rozwiązywania problemu takiego jak ten, ważne jest, aby śledzić niektóre punkty danych za pomocą argumentów metody, jednak to sprawia, że ​​metoda jest trochę bolesna do faktycznego wywoływania (stąd użycie metody pomocniczej). Mój kod jest pokazany poniżej.

//Recursive Method 
public static ArrayList<int[]> permutationsFrom(int[] start,int i, int val, ArrayList<int[]> prev) { 
    int n = start.length; 
    if (i == n) { 
     final int[] perm = start.clone(); 
     prev.add(perm); 
     return prev; 
    } 
    else if (val > n) { 
     return prev; 
    } 
    else { 
     int[] next = start.clone(); 
     next[i] = val; 
     prev.addAll(permutationsFrom(next, i+1, 1, new ArrayList<int[]>())); 
     return permutationsFrom(next, i, ++val, prev); 
    } 
} 

//Invokation 
public static ArrayList<int[]> getPermutations(int n) { 
    return permutationsFrom(new int[n], 0, 1, new ArrayList<int[]>()); 
} 

//Print the results 
public static void main(String[] args) { 
    ArrayList<int[]> perms = getPermutations(3); 
    System.out.println(perms.size()); 
    for (int[] perm : perms) { 
     for (int el : perm) { 
      System.out.print(el + " "); 
     } 
     System.out.println(); 
    } 
} 

Jak rekurencji działa:

• początek z całkowicie „nieokreślonym” permutacji: każdą możliwą wartość w każdej możliwej indeksu musi znaleźć

• w bieżącym indeksie, i , rekursywnie przywołaj metodę przechwytywania każdej wartości, val, od 1 do n

• kompletna permutacja została znaleziona , gdy i == n (tj. każdy indeks został określony od 0 do n-1), a zatem int tablicy powinien być dodany do zbioru poprzednich permutacji, prev

• jeśli val> N wszystkie możliwe wartości (od 1 do N), na indeks i została uwzględniona, a więc zbiór może być zwrócony (w którym punkt metoda będzie nadal zwiększać i i przesuwać poziomo)

Answer 6

Bit późno do tej partii, & przykro, to w C#, ale hej, jest podobny do Javy. Wszystko tu wydaje się nieco skomplikowany, więc o to funkcja, która jest dość proste, które powinny być łatwe do tłumaczenia Java -

public static List<List<T>> Permutations<T>(List<T> list) 
    { 
     List<List<T>> result = new List<List<T>>(); 

     for (int i = 0; i < list.Count(); i++) 
     { 
      T initialValue = list[i]; 
      List<T> clonedList = list.Where((item, index) => { return index != i; }).ToList(); // proper copy, less the initialValue item 

      // here's where the recursion happens, but only if there are at least 2 items left in the list 
      List<List<T>> permutations = clonedList.Count > 0 ? Permutations(clonedList) : new List<List<T>> { new List<T>() }; 

      foreach (List<T> permutation in permutations) 
      { 
       List<T> combined = new List<T> { initialValue }; 
       combined.AddRange(permutation); 

       result.Add(combined); 
      } 
     } 

     return result; 
    }