从集合中生成大小为k的所有子集

我想从一组中生成大小为k的所有子集。

例如：-say我有一组6个元素，我必须列出元素基数为3的所有子集。

我试图寻找解决方案，但那些是代码片段。 它早就完成了编码，所以我发现很难理解代码并构建一个可执行程序。

C或C ++中的完整可执行程序将非常有用。 希望使用递归的最佳解决方案。

Answer 1

找到下面的工作代码

#include #include #include using namespace std; void print( list l){ for(list::iterator it=l.begin(); it!=l.end() ; ++it) cout << " " << *it; cout< &l){ if(left==0){ print(l); return; } for(int i=index; i lt; subset(array,5,3,0,lt); return 0; } 

Answer 2

用(1<初始化一个位数组，然后使用这个算法：

http://graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation

对于大于最大整数大小的集合，您仍然可以将相同的算法应用于您自己的类型。

Answer 3

 #include  void g(int s[],int p,int k,int t[],int q=0,int r=0) { if(q==k) { for(int i=0;i 

Answer 4

可以使用递归来解决问题。 我们需要考虑以下递归的情况。

1. 选择当前元素。 现在我们递归地从剩余的集合中选择剩余的k-1个元素。（包含）
2. 未选择当前元素。 现在我们递归地从剩下的集合中选择k个元素。（排除）

以下是演示上述算法的C ++程序。

 #include #include using namespace std; void KSubset(int *a,int n,int *s,int sindex,int index,int k){ if (index>n) return; if (k==0){ for(int i=0;i 

Answer 5

最直观的算法确实会使用递归。 当你有一个集合时，我们假设你可以迭代它的所有元素。

如果我在元素e之后调用tail（e）一组所有元素。

因此，我现在想要组合（s，k）

循环遍历s中的每个元素并获取e ::组合（tail（e），k-1）其中::表示“连接到每个”

当然有时候会有这样的组合（你不在列表的末尾）。

您只需要一个主集合（一组集）来添加组合和创建方法

所以假设我们在任何地方都没有全局变量，我们可以有类似的东

 getCombinations( headset [in], tailset [in], count [in], output [append] ) 

耳机或尾部可能是空的。 count可以是0，在这种情况下我们将“耳机”写入输出（基本条件），否则我们遍历tailset中的每个元素，将其（本地）添加到耳机，使tailset（本地）成为我们元素的尾部，减去1从计数和“递归”调用该函数。

Answer 6

这是一些伪代码。 如果调用值已经存在，您可以通过在递归调用检查之前存储每个调用的值来剪切相同的递归调用。

以下算法将包含除空集之外的所有子集。

 list * subsets(string s, list * v){ if(s.length() == 1){ list.add(s); return v; } else { list * temp = subsets(s[1 to length-1], v); int length = temp->size(); for(int i=0;i 

Answer 7

  #include  #define FIN "subsets.in" #define FOUT "subsets.out" #define MAXSIZE 100 void performSubsets(int n, int k){ int i, j, s, v[ MAXSIZE ]; freopen(FOUT, "w", stdout); memset(v, 0, sizeof( v )); do { v[ n - 1 ]++; for(i = n - 1; i >= 1; i--) { if(v[ i ] > 1) { v[ i ] -= 2; v[ i - 1 ] += 1; } } s = 0; for(j = 0; j < n; j++) s += v[j]; for(j = 0; j < n; j++) if( v[ j ] && s == k) printf("%d ", (j + 1)); if(s == k) printf("\n"); } while(s < n); fclose( stdout ); } int main() { int n, k; freopen(FIN, "r", stdin); //read n and size k scanf("%d %d", &n, &k); fclose( stdin ); performSubsets(n,k); } 

使用非递归算法可以解决此问题。