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

Question

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

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

我试图寻找解决方案,但那些是代码片段.它已经很久了,我已经完成了编码,因此我发现很难理解代码并构建一个可执行程序.

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

Answer 1

找到下面的工作代码

#include<iostream>
#include<string>
#include<list>

using namespace std;

void print( list<int> l){
    for(list<int>::iterator it=l.begin(); it!=l.end() ; ++it)
            cout << " " << *it;
    cout<<endl;
}

void subset(int arr[], int size, int left, int index, list<int> &l){
    if(left==0){
        print(l);
        return;
    }
    for(int i=index; i<size;i++){
        l.push_back(arr[i]);
        subset(arr,size,left-1,i+1,l);
        l.pop_back();
    }

}     

int main(){
    int array[5]={1,2,3,4,5};
    list<int> lt;   
    subset(array,5,3,0,lt);


    return 0;
}

Answer 2

初始化一个位数组,(1<<nbits)-1然后使用此算法:

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

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

Answer 3

#include <cstdio>
void g(int s[],int p,int k,int t[],int q=0,int r=0)
{
    if(q==k)
    {
        for(int i=0;i<k;i++)
            printf("%d ",t[i]);
        printf("\n");
    }
    else
    {
        for(int i=r;i<p;i++)
        {
            t[q]=s[i];
            g(s,p,k,t,q+1,i+1);
        }
    }
}

main()
{
    int s[]={1,2,3,4,5},t[5];
    g(s,5,3,t);
}