wygenerować wszystkie możliwe kombinacje - Java

Question

Mam listę elementów {a, b, c, d} i muszę wygenerować wszystkie możliwe kombinacje, kiedy

• można wybrać dowolną liczbę przedmiotów
• kolejność nie jest ważna (ab = ba)
• zbiór pusty nie jest uważany

Jeżeli weźmiemy pod uwagę możliwości, powinno być,

n=4, number of items 
total #of combinations = 4C4 + 4C3 + 4C2 + 4C1 = 15 

użyłem następującej metody rekurencyjnej:

private void countAllCombinations (String input,int idx, String[] options) { 
    for(int i = idx ; i < options.length; i++) { 
     String output = input + "_" + options[i]; 
     System.out.println(output); 
     countAllCombinations(output,++idx, options); 
    } 
} 

public static void main(String[] args) { 
    String arr[] = {"A","B","C","D"}; 
    for (int i=0;i<arr.length;i++) { 
     countAllCombinations(arr[i], i, arr); 
    } 
} 

Czy jest bardziej efektywny sposób to zrobić, gdy rozmiar tablicy jest duża?

Answer 1

Rozważ kombinację jako sekwencję binarną, jeśli wszystkie 4 są obecne, otrzymujemy 1111, jeśli brak pierwszego alfabetu, otrzymamy 0111 itd. Tak więc dla n alfabetów będziemy mieć 2^n - 1 (od 0 nie ma w zestawie) kombinacje.

Teraz, w swojej sekwencji binarnej produkowane, jeśli kod jest 1, to element jest obecny w przeciwnym razie nie jest included.Below jest realizacja tego samego: -

String arr[] = { "A", "B", "C", "D" }; 
    int n = arr.length; 
    int N = (int) Math.pow(2d, Double.valueOf(n)); 
    for (int i = 1; i < N; i++) { 
     String code = Integer.toBinaryString(N | i).substring(1); 
     for (int j = 0; j < n; j++) { 
      if (code.charAt(j) == '1') { 
       System.out.print(arr[j]); 
      } 
     } 
     System.out.println(); 
    }