如何迭代遍历n张扑克牌的所有可能组合

Question

我该如何循环遍历标准扑克牌组中n张牌的所有组合？

- user181351

Answer 1

您需要从一个包含 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，但这是一般的想法。

- Mike Seymour

Answer 2

这个组合迭代器类是从此前的答案中派生而来的。

我进行了一些基准测试，它比你以前使用过的任何next_combination()函数都要快至少3倍。

我在MetaTrader mql4中编写了代码，用于测试外汇三角套利交易。我认为你可以很容易地将其移植到Java或C++中。

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

- Amr Ali

Answer 3

#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

- David Winiecki

---

尽管有一些非常清晰的变量名称，但这只是一堵没有情境或注释的代码墙，因此是一个不好的答案。 - Richard

我不同意Richard的观点。使用“非常清晰的变量名称”和代码结构可以使注释变得不必要。避免添加没有价值或不能提高理解的注释，因为它们很快就会与代码不同步。该解决方案易于阅读，并且是C++实现（正如Amr Ali所建议的），还演示了标准库的使用。 - Tom Wilson

Answer 4

我发现这个问题本质上与幂集问题相同。请参见编写幂集代码的问题以获得优雅的解决方案。

- Kaiyu

---

幂集枚举任意大小的子集，但这需要仅包含大小为n的子集。这是一个组合问题，而不是幂集问题。 - Raymond Chen