來自30個對象列表的4個獨特對象的每個集合和子集？

Question

我在製作算法時遇到了麻煩，該算法從約30個對象列表中產生每個集合和子集合（包括空集合），每個集合中最多包含4個對象。

我使用Java編寫，但僞代碼應該沒問題。

這是我迄今所做的：

for (int a = 0; a < Objects.length; a++) { 
    for (int b = a + 1; b < Objects.length; b++) { 
     for (int c = b + 1; c < Objects.length; c++) { 
      for (int d = c + 1; d < Objects.length; d++) { 
       // add Objects[a, b, c, d] to the Set 
       // do other stuff 
      } 
     } 
    } 
} 

但顯然這是不行的，因爲它迫使每個組4個對象（而我需要的子集用更少的元素）。

使用Google搜索這個問題產生了很多答案，但從來沒有一個產生所有的子集，並且對集合的大小有限制。

Answer 1

這應該做的伎倆：

// add the empty set [] 
for (int a = 0; a < Objects.length; a++) { 
    // add the set containing (Objects[a]) 
    for (int b = a + 1; b < Objects.length; b++) { 
     // add the set containing (Objects[a], Objects[b]) 
     for (int c = b + 1; c < Objects.length; c++) { 
      // add the set containing (Objects[a], Objects[b], Object[c]) 
      for (int d = c + 1; d < Objects.length; d++) { 
      // add the set containing (Objects[a], Objects[b], Object[c], Object[d]) 
      } 
     } 
    } 
} 

Answer 2

我做了一個相當非正統的解決這個...

// setOfSets = a set of sets 
for (int a = 0; a < Objects.length; a++) { 
    for (int b = a; b < Objects.length; b++) { 
     for (int c = b; c < Objects.length; c++) { 
      for (int d = c; d < Objects.length; d++) { 
       // s = new Set 
       // add Objects[a, b, c, d] to s 
       // add s to setOfSets 
      } 
     } 
    } 
} 

這不是很一個很聰明的解決方案，但它的工作原理。

Answer 3

如果你可以使用Google Guava library，然後使用Sets.powerSet方法和Java 8將工作：

Set<Integer> original = ...; 
Set<Set<Integer>> result = 
    Sets.powerSet(original).stream() 
     .filter(s -> s.size() <= 4) 
     .collect(Collectors.toSet()); 

正如鏈接文檔指出，這個工程只要原來設置的大小小於或等於30還值得一提的是以下提示：

性能註釋：雖然大小爲n的集合的冪集大小爲2^n，但其內存使用量僅爲O（n）。當功率組合被構造時，輸入組僅被複制。只有當功率集迭代時纔會創建單個子集，而且這些子集本身只佔用很小的恆定內存量。

Answer 4

出於好奇，我想出了一種算法，它使用位模式，並且不是（理論上）綁定到每個子集中最多4個對象。不過，由於大小爲int（32位），以下Java代碼被限制爲30個對象。我知道這種做法會導致O（2^n）的漂亮跛腳運行的複雜性（我不會推薦它用於生產），但我有點喜歡這個主意:-)

int minSize = 0; // min subset size 
int maxSize = 4; // max subset size 
int[] a = IntStream.range(0, 30).toArray(); // generate test data 

// maximum number of subsets 2^n 
int nSubsets = 1 << a.length; 
// subsets container 
// initial size could be calculated e.g.: 
// 30!/(4!*26!) + 30!/(3!*27!) + ... + 1 
List<int[]> subsets = new ArrayList<>(); 
// iterate through all possible patterns 0..2^n 
for (int mask = 0; mask < nSubsets; mask++) { 
    // bitCount should be very fast on most cpus i think 
    int bitCount = Long.bitCount(mask); 
    if (bitCount >= minSize && bitCount <= maxSize) { 
     int[] subset = new int[bitCount]; 
     for (int i = 0, j = 0; i < a.length; i++) { 
      // add element if bit is set at i 
      if ((mask & (1 << i)) != 0) { 
       subset[j++] = a[i]; 
      } 
     } 
     subsets.add(subset); 
    } 
}