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 个对象（而我需要元素较少的子集）。

用谷歌搜索这个问题会产生很多答案，但从来没有一个能产生所有子集并且对集合大小有限制的答案。

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, then using Sets.powerSet 方法并且 Java 8 将起作用：

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

如链接文档中所述，只要原始集的大小小于或等于 30，此方法就有效。还值得一提的是以下注释：

Performance notes: while the power set of a set with size n is of size 2^n, its memory usage is only O(n). When the power set is constructed, the input set is merely copied. Only as the power set is iterated are the individual subsets created, and these subsets themselves occupy only a small constant amount of memory.

Answer 4

出于好奇，我提出了一种算法，该算法使用位模式并且（理论上）不绑定到每个子集中最多 4 个对象。但是，由于 ints（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);
    }
}

30 个对象列表中的每个 4 个独特对象的集合和子集？

Every set and sub-set of 4 unique objects from a list of 30 objects?

java

pseudocode