Alle Teilmengen eines Arrays rekursiv drucken

Question

Ich möchte alle Teilmengen der generierten Arrays rekursiv in der Hauptmethode drucken.

Die folgenden Zeilen zeigen meinen Code. Ich weiß nicht, wie man die Methode subsets() rekursiv implementiert.

public class Main { 

    // Make random array with length n 
    public static int[] example(int n) { 
     Random rand = new Random(); 
     int[] example = new int[n + 1]; 
     for (int i = 1; i <= n; i++) { 
      example[i] = rand.nextInt(100); 
     } 
     Arrays.sort(example, 1, n + 1); 
     return example; 
    } 

    // Copy content of a boolean[] array into another boolean[] array 
    public static boolean[] copy(boolean[] elements, int n) { 
     boolean[] copyof = new boolean[n + 1]; 
     for (int i = 1; i <= n; i++) { 
      copyof[i] = elements[i]; 
     } 

     return copyof; 
    } 

    // Counts all subsets from 'set' 
    public static void subsets(int[] set, boolean[] includes, int k, int n) { 

     // recursive algo needed here! 

    } 

    public static void main(String[] args) { 
     // index starts with 1, -1 is just a placeholder. 
     int[] setA = {-1, 1, 2, 3, 4}; 
     boolean[] includesA = new boolean[5]; 
     subsets(setA, includesA, 1, 4); 

    } 

} 

Answer 1

Wenn es eine Option ist eine dritte Partei-Bibliothek zu verwenden, setzt der Guava-Klasse können Sie alle möglichen Teilmengen geben. Schauen Sie sich the powersets method an.

Answer 2

Hier ist eine nicht-rekursive Technik:

public List<Set<Integer>> getSubsets(Set<Integer> set) { 
    List<Set<Integer>> subsets = new ArrayList<>(); 

    int numSubsets = 1 << set.size(); // 2 to the power of the initial set size 

    for (int i = 0; i < numSubsets; i++) { 
     Set<Integer> subset = new HashSet<>(); 
     for (int j = 0; j < set.size(); j++) { 
      //If the jth bit in i is 1 
      if ((i & (1 << j)) == 1) { 
       subset.add(set.get(i)); 
      } 
     } 
     subsets.add(subset); 
    } 
    return subsets; 
} 

Wenn Sie nur einzigartige wollen (und in der Regel ungeordnete) Untergruppen, verwenden Sie einen Set<Set<Integer>> statt List<Set<Integer>>.