我该如何循环遍历标准扑克牌组中n张牌的所有组合?
N
个元素的集合中取出所有 n
个元素的组合(在本例中,N == 52
,但我将保持答案的通用性)。size_t item[n]
,满足以下条件:
0 <= item[i] < N
item[i] < item[i+1]
,这样每个组合都是唯一的子集。item[i] = i
开始。然后迭代到下一个组合:
item[n-1] < N-1
),则执行此操作。item[n-i] < N-i
)。 增加该索引,然后将所有后续索引重置为可能的最小值。item[0] == N-n
),则完成。void first_combination(size_t item[], size_t n)
{
for (size_t i = 0; i < n; ++i) {
item[i] = i;
}
}
bool next_combination(size_t item[], size_t n, size_t N)
{
for (size_t i = 1; i <= n; ++i) {
if (item[n-i] < N-i) {
++item[n-i];
for (size_t j = n-i+1; j < n; ++j) {
item[j] = item[j-1] + 1;
}
return true;
}
}
return false;
}
可以将其更加通用化,使其看起来更像std::next_permutation
,但这是一般的想法。
class CombinationsIterator
{
private:
int input_array[];
int index_array[];
int m_indices; // K
int m_elements; // N
public:
CombinationsIterator(int &src_data[], int k)
{
m_indices = k;
m_elements = ArraySize(src_data);
ArrayCopy(input_array, src_data);
ArrayResize(index_array, m_indices);
// create initial combination (0..k-1)
for (int i = 0; i < m_indices; i++)
{
index_array[i] = i;
}
}
// https://dev59.com/jlTTa4cB1Zd3GeqPtY6K
// bool next_combination(int &item[], int k, int N)
bool advance()
{
int N = m_elements;
for (int i = m_indices - 1; i >= 0; --i)
{
if (index_array[i] < --N)
{
++index_array[i];
for (int j = i + 1; j < m_indices; ++j)
{
index_array[j] = index_array[j - 1] + 1;
}
return true;
}
}
return false;
}
void get(int &items[])
{
// fill items[] from input array
for (int i = 0; i < m_indices; i++)
{
items[i] = input_array[index_array[i]];
}
}
};
//+------------------------------------------------------------------+
//| |
//+------------------------------------------------------------------+
// driver program to test above class
#define N 5
#define K 3
void OnStart()
{
int x[N] = {1, 2, 3, 4, 5};
CombinationsIterator comboIt(x, K);
int items[K];
do
{
comboIt.get(items);
printf("%s", ArrayToString(items));
} while (comboIt.advance());
}
输出:
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
#include <iostream>
#include <vector>
using namespace std;
class CombinationsIndexArray {
vector<int> index_array;
int last_index;
public:
CombinationsIndexArray(int number_of_things_to_choose_from, int number_of_things_to_choose_in_one_combination) {
last_index = number_of_things_to_choose_from - 1;
for (int i = 0; i < number_of_things_to_choose_in_one_combination; i++) {
index_array.push_back(i);
}
}
int operator[](int i) {
return index_array[i];
}
int size() {
return index_array.size();
}
bool advance() {
int i = index_array.size() - 1;
if (index_array[i] < last_index) {
index_array[i]++;
return true;
} else {
while (i > 0 && index_array[i-1] == index_array[i]-1) {
i--;
}
if (i == 0) {
return false;
} else {
index_array[i-1]++;
while (i < index_array.size()) {
index_array[i] = index_array[i-1]+1;
i++;
}
return true;
}
}
}
};
int main() {
vector<int> a;
a.push_back(1);
a.push_back(2);
a.push_back(3);
a.push_back(4);
a.push_back(5);
int k = 3;
CombinationsIndexArray combos(a.size(), k);
do {
for (int i = 0; i < combos.size(); i++) {
cout << a[combos[i]] << " ";
}
cout << "\n";
} while (combos.advance());
return 0;
}
输出:
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
我发现这个问题本质上与幂集问题相同。请参见编写幂集代码的问题以获得优雅的解决方案。