生成不同长度列表的每个powerset的算法？

给出一个列表{x1, x2, x3, x4, ..., xn}，有没有一种算法可以生成这个列表的每个子集？在这种情况下的子集必须具有长度i，其中1 <= i <= n。此外，排序并不重要，例如，这是重复的：{x3, x4, x9}与{x9, x3, x4}相同，即不会将重复项放在输出中。算法的运行时间也必须是O(n^k)，对于某些常数整数k>=0。生成不同长度列表的每个powerset的算法？

有谁知道如何做到这一点？

谢谢。

来源

2013-10-30 omega

“对于某个常数整数k> = 0，算法的运行时间必须为O（n^k）。”你需要生成的子集的数量是'2^n'。没有多项式时间算法可以产生'O（2^n）'项目。 – dasblinkenlight

这不是排列组合。对于排列，排序很重要。我认为你的意思是一个powerset，它是所有子集的集合。 – Shashank

@dasblinkenlight：实际上，OP需要生成的子集的数量是n选择i，在大O符号中，它是'O（2^i）** Oops **：我认为OP只需要生成子集为*特定*'我'，显然它*是所有*'我'。所以是的，它是'O（2^n）' – justhalf

在任何给定的子集中，原始集合的每个元素都可以存在或不存在。对于n元素列表，按顺序遍历n位二进制数，选择对应于1. 0b000 ... 000的元素为空子集。 0b111 ... 111是原始集合。中间的每个数字都是可能的子集。所有可能的子集将在列表中一次且仅包含一次。

例如，如果原来的集合是{A，B，C}：

0 -> 000 -> {} 
1 -> 001 -> {C} 
2 -> 010 -> {B} 
3 -> 011 -> {B, C} 
4 -> 100 -> {A} 
5 -> 101 -> {A, C} 
6 -> 110 -> {A, B} 
7 -> 111 -> {A, B, C}

如果需要只具有特定长度的子集，则使用的二进制1计数算法之一，以消除那些数字/子集不匹配。生成数字0到n显然是O（n）。这将它带到您使用的二进制1计数算法。没有必要消除重复，因为没有产生。

来源

2013-10-31 12:21:40 rossum

做一些谷歌搜索backtracking.Its你问一个标准的问题。

来源

2013-10-31 12:46:44 piyukr

生成不同长度列表的每个powerset的算法？

回答

相关问题