在 C++ 中创建 n 个项目的所有可能的 k 组合

Question

提问by Prannoy Mittal

There are n people numbered from 1to n. I have to write a code which produces and print all different combinations of kpeople from these n. Please explain the algorithm used for that.

有 n 个人编号从1到n。我必须编写一个代码来生成和打印k这些人的所有不同组合n。请解释用于此的算法。

Answer 1

回答by dorserg

I assume you're asking about combinations in combinatorial sense (that is, order of elements doesn't matter, so [1 2 3]is the same as [2 1 3]). The idea is pretty simple then, if you understand induction / recursion: to get all K-element combinations, you first pick initial element of a combination out of existing set of people, and then you "concatenate" this initial element with all possible combinations of K-1people produced from elements that succeed the initial element.

我假设您是在组合意义上询问组合（即元素的顺序无关紧要，因此[1 2 3]与相同[2 1 3]）。这个想法很简单，如果你理解归纳/递归：要获得所有K元素的组合，你首先从现有的一组人中挑选一个组合的初始元素，然后你“连接”这个初始元素与所有可能的组合K-1从继承初始元素的元素产生的人。

As an example, let's say we want to take all combinations of 3 people from a set of 5 people. Then all possible combinations of 3 people can be expressed in terms of all possible combinations of 2 people:

例如，假设我们想从 5 人的集合中取出 3 人的所有组合。那么 3 人的所有可能组合都可以用 2 人的所有可能组合来表示：

comb({ 1 2 3 4 5 }, 3) =
{ 1, comb({ 2 3 4 5 }, 2) } and
{ 2, comb({ 3 4 5 }, 2) } and
{ 3, comb({ 4 5 }, 2) }

Here's C++ code that implements this idea:

下面是实现这个想法的 C++ 代码：

#include <iostream>
#include <vector>

using namespace std;

vector<int> people;
vector<int> combination;

void pretty_print(const vector<int>& v) {
  static int count = 0;
  cout << "combination no " << (++count) << ": [ ";
  for (int i = 0; i < v.size(); ++i) { cout << v[i] << " "; }
  cout << "] " << endl;
}

void go(int offset, int k) {
  if (k == 0) {
    pretty_print(combination);
    return;
  }
  for (int i = offset; i <= people.size() - k; ++i) {
    combination.push_back(people[i]);
    go(i+1, k-1);
    combination.pop_back();
  }
}

int main() {
  int n = 5, k = 3;

  for (int i = 0; i < n; ++i) { people.push_back(i+1); }
  go(0, k);

  return 0;
}

And here's output for N = 5, K = 3:

这是输出N = 5, K = 3：

combination no 1:  [ 1 2 3 ] 
combination no 2:  [ 1 2 4 ] 
combination no 3:  [ 1 2 5 ] 
combination no 4:  [ 1 3 4 ] 
combination no 5:  [ 1 3 5 ] 
combination no 6:  [ 1 4 5 ] 
combination no 7:  [ 2 3 4 ] 
combination no 8:  [ 2 3 5 ] 
combination no 9:  [ 2 4 5 ] 
combination no 10: [ 3 4 5 ]

Answer 2

回答by Nikos M.

From Rosetta code

从罗塞塔代码

#include <algorithm>
#include <iostream>
#include <string>

void comb(int N, int K)
{
    std::string bitmask(K, 1); // K leading 1's
    bitmask.resize(N, 0); // N-K trailing 0's

    // print integers and permute bitmask
    do {
        for (int i = 0; i < N; ++i) // [0..N-1] integers
        {
            if (bitmask[i]) std::cout << " " << i;
        }
        std::cout << std::endl;
    } while (std::prev_permutation(bitmask.begin(), bitmask.end()));
}

int main()
{
    comb(5, 3);
}

output

输出

Analysis and idea

分析与思路

The whole point is to play with the binary representation of numbers for example the number 7in binary is 0111

重点是玩数字的二进制表示，例如二进制中的数字7是0111

So this binary representation can also be seen as an assignment listas such:

所以这个二进制表示也可以看作是一个赋值列表：

For each bit iif the bit is set (i.e is 1) means the ith item is assigned else not.

对于每个位i如果该位被设置（即为1）意味着第i个项目被分配，否则不分配。

Then by simply computing a list of consecutive binary numbers and exploiting the binary representation (which can be very fast) gives an algorithm to compute all combinations of Nover k.

然后通过简单地计算连续二进制数的列表并利用二进制表示（可以非常快）给出一种算法来计算N在k 上的所有组合。

The sortingat the end (of some implementations) is not needed. It is just a way to deterministicaly normalize the result, i.e for same numbers (N, K) and same algorithm same orderof combinations is returned

不需要（某些实现的）末尾的排序。这只是一种确定性归一化结果的方法，即对于相同的数字（N，K）和相同的算法，返回相同的组合顺序

For further reading about number representations and their relation to combinations, permutations, power sets (and other interesting stuff), have a look at Combinatorial number system, Factorial number system

要进一步了解数字表示及其与组合、排列、幂集（和其他有趣的东西）的关系，请查看Combinatorial number system, Factorial number system

Answer 3

回答by user7781254

If the number of the set would be within 32, 64 or a machine native primitive size, then you can do it with a simple bit manipulation.

如果集合的数量在 32、64 或机器本机原始大小之内，那么您可以通过简单的位操作来完成。

template<typename T>
void combo(const T& c, int k)
{
    int n = c.size();
    int combo = (1 << k) - 1;       // k bit sets
    while (combo < 1<<n) {

        pretty_print(c, combo);

        int x = combo & -combo;
        int y = combo + x;
        int z = (combo & ~y);
        combo = z / x;
        combo >>= 1;
        combo |= y;
    }
}

this example calls pretty_print() function by the dictionary order.

本示例按字典顺序调用pretty_print() 函数。

For example. You want to have 6C3 and assuming the current 'combo' is 010110. Obviously the next combo MUST be 011001. 011001 is : 010000 | 001000 | 000001

例如。你想要 6C3 并假设当前的“组合”是 010110。显然下一个组合必须是 011001。011001 是：010000 | 001000 | 000001

010000 : deleted continuously 1s of LSB side. 001000 : set 1 on the next of continuously 1s of LSB side. 000001 : shifted continuously 1s of LSB to the right and remove LSB bit.

010000：连续删除LSB端的1s。001000：LSB 侧连续 1s 的下一个置 1。000001 : LSB 连续右移 1s 并移除 LSB 位。

int x = combo & -combo;

this obtains the lowest 1.

这将获得最低的 1。

int y = combo + x;

this eliminates continuously 1s of LSB side and set 1 on the next of it (in the above case, 010000 | 001000)

这会连续消除 LSB 侧的 1s 并在其下一个设置 1（在上述情况下，010000 | 001000）

int z = (combo & ~y)

this gives you the continuously 1s of LSB side (000110).

这为您提供了 LSB 端 (000110) 的连续 1 秒。

combo = z / x;
combo >> =1;

this is for 'shifted continuously 1s of LSB to the right and remove LSB bit'.

这是为了“将 LSB 的连续 1 向右移动并删除 LSB 位”。

So the final job is to OR y to the above.

所以最后的工作是对上面的 OR y。

combo |= y;

Some simple concrete example :

一些简单的具体例子：

#include <bits/stdc++.h>

using namespace std;

template<typename T>
void pretty_print(const T& c, int combo)
{
    int n = c.size();
    for (int i = 0; i < n; ++i) {
        if ((combo >> i) & 1)
            cout << c[i] << ' ';
    }
    cout << endl;
}

template<typename T>
void combo(const T& c, int k)
{
    int n = c.size();
    int combo = (1 << k) - 1;       // k bit sets
    while (combo < 1<<n) {

        pretty_print(c, combo);

        int x = combo & -combo;
        int y = combo + x;
        int z = (combo & ~y);
        combo = z / x;
        combo >>= 1;
        combo |= y;
    }
}

int main()
{
    vector<char> c0 = {'1', '2', '3', '4', '5'};
    combo(c0, 3);

    vector<char> c1 = {'a', 'b', 'c', 'd', 'e', 'f', 'g'};
    combo(c1, 4);
    return 0;
}

result :

结果：

1 2 3 
1 2 4 
1 3 4 
2 3 4 
1 2 5 
1 3 5 
2 3 5 
1 4 5 
2 4 5 
3 4 5 
a b c d 
a b c e 
a b d e 
a c d e 
b c d e 
a b c f 
a b d f 
a c d f 
b c d f 
a b e f 
a c e f 
b c e f 
a d e f 
b d e f 
c d e f 
a b c g 
a b d g 
a c d g 
b c d g 
a b e g 
a c e g 
b c e g 
a d e g 
b d e g 
c d e g 
a b f g 
a c f g 
b c f g 
a d f g 
b d f g 
c d f g 
a e f g 
b e f g 
c e f g 
d e f g

Answer 4

回答by Ning

In Python, this is implemented as itertools.combinations

在 Python 中，这是作为 itertools.combinations 实现的

https://docs.python.org/2/library/itertools.html#itertools.combinations

In C++, such combination function could be implemented based on permutation function.

在C++中，这种组合函数可以基于置换函数来实现。

The basic idea is to use a vector of size n, and set only k item to 1 inside, then all combinations of nchoosek could obtained by collecting the k items in each permutation. Though it might not be the most efficient way require large space, as combination is usually a very large number. It's better to be implemented as a generator or put working codes into do_sth().

基本思想是使用一个大小为n的向量，只在里面设置k个项目为1，然后通过收集每个排列中的k个项目，就可以得到nchoosek的所有组合。虽然它可能不是最有效的方式，需要大空间，因为组合通常是一个非常大的数字。最好实现为生成器或将工作代码放入 do_sth()。

Code sample:

代码示例：

#include <vector>
#include <iostream>
#include <iterator>
#include <algorithm>

using namespace std;

int main(void) {

  int n=5, k=3;

  // vector<vector<int> > combinations;
 vector<int> selected;
 vector<int> selector(n);
 fill(selector.begin(), selector.begin() + k, 1);
 do {
     for (int i = 0; i < n; i++) {
      if (selector[i]) {
            selected.push_back(i);
      }
     }
     //     combinations.push_back(selected);
         do_sth(selected);
     copy(selected.begin(), selected.end(), ostream_iterator<int>(cout, " "));
     cout << endl;
     selected.clear();
 }
 while (prev_permutation(selector.begin(), selector.end()));

  return 0;
}

and the output is

输出是

This solution is actually a duplicate with Generating combinations in c++

这个解决方案实际上是在 c++ 中生成组合的副本

Answer 5

回答by android927

Here is an algorithm i came up with for solving this problem. You should be able to modify it to work with your code.

这是我为解决此问题而提出的算法。您应该能够修改它以使用您的代码。

void r_nCr(const unsigned int &startNum, const unsigned int &bitVal, const unsigned int &testNum) // Should be called with arguments (2^r)-1, 2^(r-1), 2^(n-1)
{
    unsigned int n = (startNum - bitVal) << 1;
    n += bitVal ? 1 : 0;

    for (unsigned int i = log2(testNum) + 1; i > 0; i--) // Prints combination as a series of 1s and 0s
        cout << (n >> (i - 1) & 1);
    cout << endl;

    if (!(n & testNum) && n != startNum)
        r_nCr(n, bitVal, testNum);

    if (bitVal && bitVal < testNum)
        r_nCr(startNum, bitVal >> 1, testNum);
}

You can see an explanation of how it works here.

您可以在此处查看其工作原理的说明。

Answer 6

回答by Bob Bryan

I have written a class in C# to handle common functions for working with the binomial coefficient, which is the type of problem that your problem falls under. It performs the following tasks:

我在 C# 中编写了一个类来处理处理二项式系数的常用函数，这是您的问题所属的问题类型。它执行以下任务：

Outputs all the K-indexes in a nice format for any N choose K to a file. The K-indexes can be substituted with more descriptive strings or letters. This method makes solving this type of problem quite trivial.
Converts the K-indexes to the proper index of an entry in the sorted binomial coefficient table. This technique is much faster than older published techniques that rely on iteration. It does this by using a mathematical property inherent in Pascal's Triangle. My paper talks about this. I believe I am the first to discover and publish this technique.
Converts the index in a sorted binomial coefficient table to the corresponding K-indexes. I believe it is also faster than the other solutions.
Uses Mark Dominusmethod to calculate the binomial coefficient, which is much less likely to overflow and works with larger numbers.
The class is written in .NET C# and provides a way to manage the objects related to the problem (if any) by using a generic list. The constructor of this class takes a bool value called InitTable that when true will create a generic list to hold the objects to be managed. If this value is false, then it will not create the table. The table does not need to be created in order to perform the 4 above methods. Accessor methods are provided to access the table.
There is an associated test class which shows how to use the class and its methods. It has been extensively tested with 2 cases and there are no known bugs.

将任何 N 选择 K 的所有 K 索引以一种很好的格式输出到一个文件中。K-indexes 可以用更具描述性的字符串或字母代替。这种方法使得解决这类问题变得非常简单。
将 K 索引转换为已排序二项式系数表中条目的正确索引。这种技术比依赖迭代的较旧的已发布技术快得多。它通过使用帕斯卡三角形中固有的数学属性来实现这一点。我的论文谈到了这一点。我相信我是第一个发现并发布这项技术的人。
将排序的二项式系数表中的索引转换为相应的 K 索引。我相信它也比其他解决方案更快。
使用Mark Dominus方法计算二项式系数，该方法不太可能溢出并且适用于较大的数字。
该类是用 .NET C# 编写的，并提供了一种通过使用通用列表来管理与问题（如果有）相关的对象的方法。此类的构造函数采用名为 InitTable 的 bool 值，当为 true 时，将创建一个通用列表来保存要管理的对象。如果此值为 false，则不会创建表。为了执行上述 4 种方法，不需要创建该表。提供了访问器方法来访问表。
有一个关联的测试类，它显示了如何使用该类及其方法。它已经用 2 个案例进行了广泛的测试，没有已知的错误。

To read about this class and download the code, see Tablizing The Binomial Coeffieicent.

要阅读有关此类的信息并下载代码，请参阅Tablizing The Binomial Coeffiecent。

It should be pretty straight forward to port the class over to C++.

将类移植到 C++ 应该非常简单。

The solution to your problem involves generating the K-indexes for each N choose K case. For example:

您的问题的解决方案涉及为每个 N 选择 K 情况生成 K 索引。例如：

int NumPeople = 10;
int N = TotalColumns;
// Loop thru all the possible groups of combinations.
for (int K = N - 1; K < N; K++)
{
   // Create the bin coeff object required to get all
   // the combos for this N choose K combination.
   BinCoeff<int> BC = new BinCoeff<int>(N, K, false);
   int NumCombos = BinCoeff<int>.GetBinCoeff(N, K);
   int[] KIndexes = new int[K];
   BC.OutputKIndexes(FileName, DispChars, "", " ", 60, false);
   // Loop thru all the combinations for this N choose K case.
   for (int Combo = 0; Combo < NumCombos; Combo++)
   {
      // Get the k-indexes for this combination, which in this case
      // are the indexes to each person in the problem set.
      BC.GetKIndexes(Loop, KIndexes);
      // Do whatever processing that needs to be done with the indicies in KIndexes.
      ...
   }
}

The OutputKIndexes method can also be used to output the K-indexes to a file, but it will use a different file for each N choose K case.

OutputKIndexes 方法也可用于将 K-indexes 输出到文件，但它会为每个 N 选择 K 情况使用不同的文件。

Answer 7

回答by Arpit Gupta

It can also be done using backtracking by maintaining a visited array.

也可以通过维护访问过的数组使用回溯来完成。

void foo(vector<vector<int> > &s,vector<int> &data,int go,int k,vector<int> &vis,int tot)
{

    vis[go]=1;
    data.push_back(go);
    if(data.size()==k)
    {
        s.push_back(data);
        vis[go]=0;
    data.pop_back();
        return;
    }

    for(int i=go+1;i<=tot;++i)
    {
       if(!vis[i])
       {
           foo(s,data,i,k,vis,tot);
       }
    }
    vis[go]=0;
    data.pop_back();
}


vector<vector<int> > Solution::combine(int n, int k) {
   vector<int> data;
   vector<int> vis(n+1,0);
   vector<vector<int> > sol;
   for(int i=1;i<=n;++i)
   {
       for(int i=1;i<=n;++i) vis[i]=0;
   foo(sol,data,i,k,vis,n);
   }
   return sol;

}

Answer 8

回答by IntegratedHen

I thought my simple "all possible combination generator" might help someone, i think its a really good example for building something bigger and better

我认为我简单的“所有可能的组合生成器”可能会帮助某人，我认为这是构建更大更好的东西的一个很好的例子

you can change N(characters)to any you like by just removing/adding from string array(you can change it to int as well).Current amount of characters is 36

您只需从字符串数组中删除/添加即可将 N （字符）更改为您喜欢的任何字符（您也可以将其更改为 int）。当前字符数为 36

you can also change K(size of the generated combinations)by just adding more loops, for each element, there must be one extra loop. Current size is 4

您还可以通过添加更多循环来更改 K （生成组合的大小），对于每个元素，必须有一个额外的循环。当前大小为 4

#include<iostream>

using namespace std;

int main() {
string num[] = {"0","1","2","3","4","5","6","7","8","9","a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z" };

for (int i1 = 0; i1 < sizeof(num)/sizeof(string); i1++) {
    for (int i2 = 0; i2 < sizeof(num)/sizeof(string); i2++) {
        for (int i3 = 0; i3 < sizeof(num)/sizeof(string); i3++) {
            for (int i4 = 0; i4 < sizeof(num)/sizeof(string); i4++) {
                cout << num[i1] << num[i2] << num[i3] << num[i4] << endl;
            }
        }
    }
}}

Result

结果

just keep in mind that the amount of combinations can be ridicules.

请记住，组合的数量可能会被嘲笑。

Answer 9

回答by jaolho

Behind the link below is a generic C# answer to this problem: How to format all combinations out of a list of objects. You can limit the results only to the length of k pretty easily.

下面的链接后面是这个问题的通用 C# 答案：如何格式化对象列表中的所有组合。您可以很容易地将结果限制为 k 的长度。

https://stackoverflow.com/a/40417765/2613458

在 C++ 中创建 n 个项目的所有可能的 k 组合

提问by Prannoy Mittal

回答by dorserg

回答by Nikos M.

回答by user7781254

回答by Ning

回答by android927

回答by Bob Bryan

回答by Arpit Gupta

回答by IntegratedHen

回答by jaolho

相关推荐

最近更新

标签

在 C++ 中创建 n 个项目的所有可能的 k 组合

提问by Prannoy Mittal

回答by dorserg

回答by Nikos M.

回答by user7781254

回答by Ning

回答by android927

回答by Bob Bryan

回答by Arpit Gupta

回答by IntegratedHen

回答by jaolho

相关推荐

C++ 使 std::vector 分配对齐的内存

C++ 创建无重复的随机数序列

C++ 什么是复制省略和返回值优化？

C++ 如何在 Linux 或 Windows 中为 OS X 编译？

相关推荐

最近更新

标签