1从到有 n 个人n。我必须编写一个代码来生成和打印k这些人的所有不同组合n。请解释用于此的算法。
问问题
176480 次
13 回答
76
我假设您在组合意义上询问组合（即元素的顺序无关紧要，因此[1 2 3]与 相同[2 1 3]）。那么这个想法很简单，如果你理解归纳/递归：要获得所有K元素组合，你首先从现有的一组人中选择一个组合的初始元素，然后你将这个初始元素与所有可能的组合“连接”K-1人从继承初始元素的元素中产生。
例如，假设我们要从 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) }
下面是实现这个想法的 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;
}
这是输出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 ]
于 2012-10-20T20:45:35.967 回答
67
#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);
}
输出
0 1 2
0 1 3
0 1 4
0 2 3
0 2 4
0 3 4
1 2 3
1 2 4
1 3 4
2 3 4
分析与思路
重点是玩数字的二进制表示，例如二进制中的数字7是0111
所以这个二进制表示也可以看作是一个赋值列表：
对于每个位i如果该位被设置（即为1）意味着第i个项目被分配，否则不被分配。
然后通过简单地计算一个连续二进制数的列表并利用二进制表示（可以非常快）给出一种算法来计算N超过k的所有组合。
不需要（某些实现的）末尾的排序。这只是一种确定性归一化结果的方法，即对于相同的数字（N，K）和相同的算法，返回相同的组合顺序
要进一步了解数字表示及其与组合、排列、幂集（和其他有趣的东西）的关系，请查看组合数系统、阶乘数系统
PS：您可能想查看我的组合框架 Abacus，它可以有效地计算多种类型的组合对象，并且它的例程（最初在 JavaScript 中）可以很容易地适应许多其他语言。
于 2015-02-24T14:41:13.417 回答
15
如果集合的数量在 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;
}
}
此示例按字典顺序调用 pretty_print() 函数。
例如。您想要 6C3 并假设当前的“组合”是 010110。显然下一个组合必须是 011001。011001 是：010000 | 001000 | 000001
010000 : LSB 侧连续删除 1s。001000 : LSB 侧连续 1s 的下一个置 1。000001 : LSB 连续右移 1s 并移除 LSB 位。
int x = combo & -combo;
这获得了最低的1。
int y = combo + x;
这会连续消除 LSB 侧的 1，并在其下一个设置 1（在上述情况下，010000 | 001000）
int z = (combo & ~y)
这为您提供了 LSB 端 (000110) 的连续 1。
combo = z / x;
combo >> =1;
这是用于“将 LSB 连续向右移动 1 并删除 LSB 位”。
所以最后的工作是 OR y 到上面。
combo |= y;
一些简单的具体例子：
#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;
}
结果 ：
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
于 2017-03-28T17:12:57.700 回答
7
在 Python 中，这被实现为 itertools.combinations
https://docs.python.org/2/library/itertools.html#itertools.combinations
在C++中，这种组合函数可以基于置换函数来实现。
其基本思想是使用一个大小为n的向量，并在里面只设置k项为1，那么nchoosek的所有组合可以通过收集每个排列中的k项得到。虽然它可能不是最有效的方式，但需要大空间，因为组合通常是一个非常大的数字。最好作为生成器实现或将工作代码放入do_sth()。
代码示例：
#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;
}
输出是
0 1 2
0 1 3
0 1 4
0 2 3
0 2 4
0 3 4
1 2 3
1 2 4
1 3 4
2 3 4
这个解决方案实际上是与 在 C++ 中生成组合的副本
于 2014-05-14T19:22:24.310 回答
2
这是我想出的解决这个问题的算法。您应该能够修改它以使用您的代码。
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);
}
您可以在此处查看其工作原理的说明。
于 2015-02-03T20:02:21.000 回答
1
我在 C# 中编写了一个类来处理处理二项式系数的常用函数，这是您的问题所属的问题类型。它执行以下任务：
将任何 N 选择 K 的所有 K 索引以良好的格式输出到文件。K-indexes 可以替换为更具描述性的字符串或字母。这种方法使得解决这类问题变得非常简单。
将 K 索引转换为已排序二项式系数表中条目的正确索引。这种技术比依赖迭代的旧已发布技术快得多。它通过使用帕斯卡三角形固有的数学属性来做到这一点。我的论文谈到了这一点。我相信我是第一个发现并发表这种技术的人。
将已排序二项式系数表中的索引转换为相应的 K 索引。我相信它也比其他解决方案更快。
使用Mark Dominus方法计算二项式系数，它不太可能溢出并且适用于更大的数字。
该类是用 .NET C# 编写的，并提供了一种通过使用通用列表来管理与问题相关的对象（如果有）的方法。此类的构造函数采用一个名为 InitTable 的 bool 值，当它为 true 时，将创建一个通用列表来保存要管理的对象。如果此值为 false，则不会创建表。无需创建表即可执行上述 4 种方法。提供了访问器方法来访问表。
有一个关联的测试类，它显示了如何使用该类及其方法。它已经用 2 个案例进行了广泛的测试，并且没有已知的错误。
要了解此类并下载代码，请参阅制表二项式系数。
将类移植到 C++ 应该非常简单。
您的问题的解决方案涉及为每个 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.
...
}
}
OutputKIndexes 方法也可用于将 K-indexes 输出到文件，但它会为每个 N 选择 K 的情况使用不同的文件。
于 2012-10-20T19:44:29.927 回答
1
您可以使用 Howard Hinnant 的组合库中的“count_each_combination”和“for_each_combination”函数来生成从 n 中取 k 的所有组合。
#include <vector>
#include "combinations.h"
std::vector<std::vector<u_int8_t> >
combinationsNoRepetitionAndOrderDoesNotMatter (long int subsetSize, std::vector<uint8_t> setOfNumbers)
{
std::vector<std::vector<u_int8_t> > subsets{};
subsets.reserve (count_each_combination (setOfNumbers.begin (), setOfNumbers.begin () + subsetSize, setOfNumbers.end ()));
for_each_combination (setOfNumbers.begin (), setOfNumbers.begin () + subsetSize, setOfNumbers.end (), [&subsets] (auto first, auto last) {
subsets.push_back (std::vector<uint8_t>{ first, last });
return false;
});
return subsets;
}
int main(){
combinationsNoRepetitionAndOrderDoesNotMatter (6, { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36 });
}
Intel(R) Core(TM) i5-8600K CPU @ 3.60GHz 的基准测试：
g++
benchmark name samples iterations estimated
mean low mean high mean
std dev low std dev high std dev
-------------------------------------------------------------------------------
combinations no repetition and
order does not matter 6 from 36 100 1 10.2829 s
92.5451 ms 92.3971 ms 92.9411 ms
1.15617 ms 532.604 us 2.48342 ms
铿锵++
benchmark name samples iterations estimated
mean low mean high mean
std dev low std dev high std dev
-------------------------------------------------------------------------------
combinations no repetition and
order does not matter 6 from 36 100 1 11.0786 s
88.1275 ms 87.8212 ms 89.3204 ms
2.82107 ms 400.665 us 6.67526 ms
于 2022-02-02T13:15:41.050 回答
0
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.
于 2016-11-04T10:27:24.920 回答
0
这个模板化函数使用任何类型的向量作为输入。
组合作为向量的向量返回。
/*
* Function return all possible combinations of k elements from N-size inputVector.
* The result is returned as a vector of k-long vectors containing all combinations.
*/
template<typename T> std::vector<std::vector<T>> getAllCombinations(const std::vector<T>& inputVector, int k)
{
std::vector<std::vector<T>> combinations;
std::vector<int> selector(inputVector.size());
std::fill(selector.begin(), selector.begin() + k, 1);
do {
std::vector<int> selectedIds;
std::vector<T> selectedVectorElements;
for (int i = 0; i < inputVector.size(); i++) {
if (selector[i]) {
selectedIds.push_back(i);
}
}
for (auto& id : selectedIds) {
selectedVectorElements.push_back(inputVector[id]);
}
combinations.push_back(selectedVectorElements);
} while (std::prev_permutation(selector.begin(), selector.end()));
return combinations;
}
于 2021-03-11T11:11:54.773 回答
0
为了使其更完整，以下答案涵盖了数据集包含重复值的情况。该函数的编写方式接近于 std::next_permutation() 的风格，因此易于跟进。
template< class RandomIt >
bool next_combination(RandomIt first, RandomIt n_first, RandomIt last)
{
if (first == last || n_first == first || n_first == last)
{
return false;
}
RandomIt it_left = n_first;
--it_left;
RandomIt it_right = n_first;
bool reset = false;
while (true)
{
auto it = std::upper_bound(it_right, last, *it_left);
if (it != last)
{
std::iter_swap(it_left, it);
if (reset)
{
++it_left;
it_right = it;
++it_right;
std::size_t left_len = std::distance(it_left, n_first);
std::size_t right_len = std::distance(it_right, last);
if (left_len < right_len)
{
std::swap_ranges(it_left, n_first, it_right);
std::rotate(it_right, it_right+left_len, last);
}
else
{
std::swap_ranges(it_right, last, it_left);
std::rotate(it_left, it_left+right_len, n_first);
}
}
return true;
}
else
{
reset = true;
if (it_left == first)
{
break;
}
--it_left;
it_right = n_first;
}
}
return false;
}
完整的数据集在 [first, last) 范围内表示。当前组合表示在范围 [first, n_first) 中，范围 [n_first, last) 包含当前组合的补集。
由于组合与其顺序无关，因此 [first, n_first) 和 [n_first, last) 保持升序以避免重复。
该算法通过与右侧大于 A 的第一个值 B 交换来增加左侧的最后一个值 A。交换后，双方仍然是有序的。如果右侧不存在这样的值B，那么我们开始考虑增加左侧倒数第二个，直到左侧的所有值不小于右侧。
通过以下代码从集合中绘制 2 个元素的示例：
std::vector<int> seq = {1, 1, 2, 2, 3, 4, 5};
do
{
for (int x : seq)
{
std::cout << x << " ";
}
std::cout << "\n";
} while (next_combination(seq.begin(), seq.begin()+2, seq.end()));
给出：
1 1 2 2 3 4 5
1 2 1 2 3 4 5
1 3 1 2 2 4 5
1 4 1 2 2 3 5
1 5 1 2 2 3 4
2 2 1 1 3 4 5
2 3 1 1 2 4 5
2 4 1 1 2 3 5
2 5 1 1 2 3 4
3 4 1 1 2 2 5
3 5 1 1 2 2 4
4 5 1 1 2 2 3
如果需要，检索前两个元素作为组合结果是很简单的。
于 2020-07-17T12:21:28.823 回答
0
它也可以通过维护访问数组使用回溯来完成。
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;
}
于 2018-06-11T08:20:11.810 回答
0
我认为我简单的“所有可能的组合生成器”可能会对某人有所帮助，我认为它是构建更大更好的东西的一个很好的例子
您可以通过从字符串数组中删除/添加将N （字符）更改为您喜欢的任何字符（您也可以将其更改为 int）。当前字符数为 36
您还可以通过添加更多循环来更改 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;
}
}
}
}}
结果
0: A A A
1: B A A
2: C A A
3: A B A
4: B B A
5: C B A
6: A C A
7: B C A
8: C C A
9: A A B
...
请记住，组合的数量可能会被嘲笑。
- 更新 -
生成所有可能组合的更好方法是使用此代码，可以在代码的“变量”部分轻松调整和配置。
#include<iostream>
#include<math.h>
int main() {
//VARIABLES
char chars[] = { 'A', 'B', 'C' };
int password[4]{0};
//SIZES OF VERIABLES
int chars_length = sizeof(chars) / sizeof(char);
int password_length = sizeof(password) / sizeof(int);
//CYCKLE TROUGH ALL OF THE COMBINATIONS
for (int i = 0; i < pow(chars_length, password_length); i++){
//CYCKLE TROUGH ALL OF THE VERIABLES IN ARRAY
for (int i2 = 0; i2 < password_length; i2++) {
//IF VERIABLE IN "PASSWORD" ARRAY IS THE LAST VERIABLE IN CHAR "CHARS" ARRRAY
if (password[i2] == chars_length) {
//THEN INCREMENT THE NEXT VERIABLE IN "PASSWORD" ARRAY
password[i2 + 1]++;
//AND RESET THE VERIABLE BACK TO ZERO
password[i2] = 0;
}}
//PRINT OUT FIRST COMBINATION
std::cout << i << ": ";
for (int i2 = 0; i2 < password_length; i2++) {
std::cout << chars[password[i2]] << " ";
}
std::cout << "\n";
//INCREMENT THE FIRST VERIABLE IN ARRAY
password[0]++;
}}
于 2019-12-04T21:00:09.667 回答
0
该解决方案的基本思想是模仿您在高中时手动枚举所有组合而不重复的方式。设 com 为长度为 k 的 List[int]，而 nums 为给定 n 项的 List[int]，其中 n >= k。思路如下：
for x[0] in nums[0,...,n-1]
for x[1] in nums[idx_of_x[0] + 1,..,n-1]
for x[2] in nums [idx_of_x[1] + 1,...,n-1]
..........
for x[k-1] in nums [idx_of_x[k-2]+1, ..,n-1]
显然，k 和 n 是可变参数，这使得无法编写显式的多个嵌套 for 循环。这就是递归解决问题的地方。语句len(com) + len(nums[i:]) >= k检查剩余的未访问前向列表是否可以提供 k iitems。向前，我的意思是你不应该向后走，以避免重复组合，它由相同的一组项目组成，但顺序不同。换句话说，在这些不同的顺序中，我们可以通过向前扫描列表来选择这些项目出现在列表中的顺序。更重要的是，此测试子句在内部修剪递归树，使其仅包含n choose k递归调用。因此，运行时间为 O(· n choose k)。
from typing import List
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
assert 1 <= n <= 20
assert 1 <= k <= n
com_sets = []
self._combine_recurse(k, list(range(1, n+1)), [], com_sets)
return com_sets
def _combine_recurse(self, k: int, nums: List[int], com: List[int], com_set: List[List[int]]):
"""
O(C_n^k)
"""
if len(com) < k:
for i in range(len(nums)):
# Once again, don't com.append() since com should not be global!
if len(com) + len(nums[i:]) >= k:
self._combine_recurse(k, nums[i+1:], com + [nums[i]], com_set)
else:
if len(com) == k:
com_set.append(com)
print(com)
sol = Solution()
sol.combine(5, 3)
[1, 2, 3]
[1, 2, 4]
[1, 2, 5]
[1, 3, 4]
[1, 3, 5]
[1, 4, 5]
[2, 3, 4]
[2, 3, 5]
[2, 4, 5]
[3, 4, 5]
于 2020-10-20T20:43:59.737 回答