C++ 从集合中生成大小为 k 的所有子集
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/4555565/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
generate all subsets of size k from a set
提问by Kumar
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++ 可执行程序会很有帮助。希望使用递归的最佳解决方案。
回答by user843453
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;
}
回答by R.. GitHub STOP HELPING ICE
Initialize a bit array with (1<<nbits)-1and 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.
对于大于最大整数大小的集合，您仍然可以将相同的算法应用于您自己的类型。
回答by moinudin
#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);
}
回答by Rohit Gurunath
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)
- The current element is not chosen . Now we recursively choose k elements from the remaining set.(exclusion)
- 当前元素被选中。现在我们从剩余的集合中递归地选择剩余的 k-1 个元素。（包含）
- 当前元素未被选中。现在我们递归地从剩余的集合中选择 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;
}
回答by Adrian Statescu
#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.
这个问题可以使用非递归算法解决。
回答by k06a
My old code gives the following result:
我的旧代码给出了以下结果：
111000
110100
110010
110001
101100
101010
101001
100110
100101
100011
011100
011010
011001
010110
010101
010011
001110
001101
001011
000111
Enough optimized:
足够优化：
#include <iostream>
int firstPermutation(int n, int k) {
return ((1 << k) - 1) << (n - k);
}
int shiftLast1(int a) {
return (a - 1) ^ ((a^(a - 1)) >> 2);
}
int add1AfterLast1(int a) {
return a | (((a^(a - 1)) + 1) >> 2);
}
int nextPermutation(int a) {
if ((a & (a + 1)) == 0) {
return 0;
}
if (a & 1) {
return add1AfterLast1(nextPermutation(a >> 1) << 1);
}
else {
return shiftLast1(a);
}
}
int main() {
int n = 6;
int k = 3;
int a = firstPermutation(n, k);
do {
for (int i = 0; i < n; i++) {
std::cout << ((a >> (n - 1 - i)) & 1);
}
std::cout << std::endl;
} while ((a = nextPermutation(a)));
}
回答by CashCow
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，在这种情况下，我们将“headset”写入输出（基本条件），否则我们遍历 tailset 中的每个元素，将其（本地）添加到耳机中，使 tailset（本地）成为元素的尾部，减去 1通过调用函数从计数和“递归”。
回答by kofhearts
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;
}
}
回答by SajadAlipour
Here is an Iterative solution :
这是一个迭代解决方案：
#include <stdio.h>
#include <stdlib.h>
void printer(int locations[],int a[],int r)
{
int i;
for(i=0; i<r; i++)
{
int x=locations[i];
printf("%d ",a[x]);
}
printf("\n");
}
int main()
{
int a[100000];
int locations[1000];
int i,n,r;
printf("Enter N: ");
scanf("%d",&n);
printf("Enter K: ");
scanf("%d",&r);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
for(i=0; i<r; i++)
locations[i]=i;
printer(locations,a,r);
while(locations[0]<n-r)
{
for(i=r-1; i>0; i--)
{
if(locations[i-1]<n-r+i-1)
{
if(locations[i]<n-r+i)
{
locations[i]++;
printer(locations,a,r);
break;
}
else
{
locations[i-1]++;
int j;
for(j=i; j<r; j++)
{
locations[j]=locations[j-1]+1;
}
printer(locations,a,r);
break;
}
}
}
}
return 0;
}
