algorithm - 如何找到集合的所有可能的 n 元素子集？

Question

对于一组k元素，我需要找到所有可能的n元素子集(n < k)。

我应该如何解决这个问题？

只是一个建议会有所帮助谢谢！

Answer 1

我在 topcoder 的算法教程中看到了这一点。花点时间了解它是如何工作的。

遍历 {0, 1, ... N-1} 的所有 k 元素子集

   int s = (1 << k) - 1;
   while (!(s & 1 << N))
   {
     // do stuff with s
     int lo = s & ~(s - 1);       // lowest one bit
     int lz = (s + lo) & ~s;      // lowest zero bit above lo
     s |= lz;                     // add lz to the set
     s &= ~(lz - 1);              // reset bits below lz
     s |= (lz / lo / 2) - 1;      // put back right number of bits at end
   }

Answer 2

当我需要在 Java 中获取字符串 ArrayList 的所有组合（或子集）时，我使用了这种方法。

public static List<List<String>> powerset(ArrayList<String> list) {
        List<List<String>> ps = new ArrayList<List<String>>();
        ps.add(new ArrayList<String>());

        // for every item in the original list
        for (String item : list) {
            List<List<String>> newPs = new ArrayList<List<String>>();

            for (List<String> subset : ps) {
                // copy all of the current powerset's subsets
                newPs.add(subset);

                // plus the subsets appended with the current item
                List<String> newSubset = new ArrayList<String>(subset);
                newSubset.add(item);
                newPs.add(newSubset);
            }

            // powerset is now powerset of list.subList(0, list.indexOf(item)+1)
            ps = newPs;
        }
        return ps;
}

这是一项昂贵的操作，可能不是适合您情况的完美解决方案。但如果我想快速提出解决方案，我会按照这些思路做一些事情。您可以检查 是否newSubset小于n，您想要的子集的大小，如果小于 ，则仅添加item到它n。这将阻止您生成大于 n 的子集。最后，您可以遍历ps并删除任何小于n. 同样，这个解决方案绝不是完美的......但它应该可以解决问题

Answer 3

句子：集合 A 是小于 10 的整数的集合。

写成：

A={0,1,2,3,4,5,6,7,8,9}

它被称为列表或名册方法