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

I want to generate all the subsets of size k from a set.

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

eg:-say I have a set of 6 elements, I have to list all the subsets in which the cardinality of elements is 3.

假设我有一组6个元素，我必须列出所有元素的基数为3的子集。

I tried looking for solution,but those are code snippets. Its been long since I have done coding,so I find it hard to understand the code and construct a executable program around it.

我尝试寻找解决方案，但这些是代码片段。我已经很久没有编写过代码了，所以我发现很难理解代码并围绕它构建一个可执行程序。

A complete executable program in C or C++ will be quite helpful. Hoping of an optimal solution using recursion.

用C或c++编写一个完整的可执行程序将非常有用。希望用递归得到最优解。

7 个解决方案

#1

Find a working code below

找到下面的工作代码

#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;
}

#2

Initialize a bit array with (1<<nbits)-1 and then use this algorithm:

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

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

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

For sets larger than the maximum integer size, you can still apply the same algorithm to your own type.

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

#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);
}

#4

The Problem can be solved using recursion. We need to consider the following cases for recursion.

这个问题可以用递归来解决。对于递归，我们需要考虑以下情况。

The current element is chosen . Now we recursively choose the remaining k-1 elements from the remaining set .(inclusion)
选择当前元素。现在我们递归地从剩下的集合中选择剩下的k-1元素。
The current element is not chosen . Now we recursively choose k elements from the remaining set.(exclusion)
不选择当前元素。现在我们递归地从剩下的集合中选择k个元素。

Following is a C++ program that demonstrates the above Algorithm.

下面是一个演示上述算法的c++程序。

#include<iostream>
#include<cstdio>

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<sindex;i++)
            printf(" %d ",s[i]);
        printf("\n");
        return ;
        }

    s[sindex]=a[index];
    KSubset(a,n,s,sindex+1,index+1,k-1);
    KSubset(a,n,s,sindex,index+1,k);
}


int main(){

    int a[]={1,2,3,4,5};
    int s[3];
    KSubset(a,5,s,0,0,3);

    return 0;
}

#5

The most intuitive algorithm would indeed use recursion. When you have a set, we will assume you can iterate over all its elements.

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

If I call tail(e) a set of all the elements after element e.

如果我调用tail(e)元素e后面所有元素的集合。

Thus I want right now combinations(s,k)

现在我想要组合(s,k)

loop over each element in s and get e :: combinations(tail(e), k-1) where :: means "concatenated to each of"

对s中的每个元素进行循环，得到e::组合(tail(e)， k-1)其中::表示“连接到每个

Of course sometimes there will be no such combinations (you are off the end of the list).

当然，有时不会有这样的组合(您不在列表的末尾)。

You just need a master collection (set of sets) to add your combinations to and a way to create

您只需要一个主集合(一组集合)来添加您的组合和创建方法

So assuming we have no globals anywhere we can have something like:

假设我们没有全局变量，我们可以有:

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

headset or tailset could be empty. count could be 0, in which case we write "headset" to output (the base condition) otherwise we iterate through each element in tailset, adding it (locally) to headset, make tailset (locally) the tail of our element, subtract 1 from count and "recurse" by calling the function.

耳机或尾灯可以是空的。count可以是0，在这种情况下，我们将“头戴式”写入输出(基本条件)，否则我们将遍历尾集中的每个元素，将其(本地)添加到耳机中，将tailset(本地)设置为元素的尾部，从count中减去1，通过调用函数“递归”。

#6

Here's some pseudocode. You can cut same recursive calls by storing the values for each call as you go and before recursive call checking if the call value is already present.

这里有一些伪代码。您可以在执行过程中存储每个调用的值，并在递归调用检查调用值是否已经存在之前，减少相同的递归调用。

The following algorithm will have all the subsets excluding the empty set.

下面的算法将包含所有的子集，不包括空集。

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<length;i++){
            temp.add(s[0]+temp[i]);
        }

        list.add(s[0]);
        return temp;
    }
}

#7

 #include <stdio.h>
 #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);

}

This problem can be solved using an algorithm non-recursive.

这个问题可以用非递归算法来解决。

#1