生成不同長度列表的每個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的算法？

回答

相關問題