c - 32 副牌的具体排列(C 语言)

Question

我想生成 32 张牌的所有排列，我将牌表示为数字 0-7，所以我不关心牌的颜色。游戏非常简单(将牌组分成两组，比较两张牌，将两张牌添加到更大的牌组中)。我已经编写了游戏的这一部分，但是牌组现在是随机生成的，我想查看牌的所有可能性，并对其进行一些统计。我该如何编码生成这张卡？我完全不知道如何编码。

Answer 1

因为我正在研究 Aaron Williams 2009 年的论文“Loopless Generation of Multiset Permutations by Prefix Shifts”，所以我将贡献他的算法的一个版本，它精确地解决了这个问题。我相信它比通常针对此问题引用的标准 C++ next_permutation 更快，因为它不依赖于搜索枢轴点的输入 vector 。但需要更广泛的基准测试才能得出明确的答案；它很可能最终会移动更多数据。

Williams 的算法实现通过将排列存储在链表中来避免数据移动，这使得只需修改两个 next 即可实现“前缀移位”(将 vector 的前缀旋转一个位置) 指针。这使得算法无循环。

我的版本在几个方面有所不同。

• 首先，它使用普通数组来存储值，这意味着移位确实需要循环。另一方面，它避免了必须实现链表数据类型，并且许多操作在数组上速度更快。

• 其次，它使用后缀移位而不是前缀移位；实际上，它产生每个排列的相反结果(与威廉姆斯的实现相比)。我这样做是因为它简化了起始条件的描述。

• 最后，它只执行一个排列步骤。 Williams 算法的优点之一是排列序列的状态可以封装在单个索引值中(当然还有排列本身)。此实现返回要提供给下一次调用的状态。 (由于状态变量最后将为 0，因此返回值兼作终止指示符。)

代码如下:

/* Do a single permutation of v in reverse coolex order, using
 * a modification of Aaron Williams' loopless shift prefix algorithm.
 * v must have length n. It may have repeated elements; the permutations
 * generated will be unique.
 * For the first call, v must be sorted into non-descending order and the
 * third parameter must be 1. For subsequent calls, the third parameter must
 * be the return value of the previous call. When the return value is 0,
 * all permutations have been generated.
 */
unsigned multipermute_step(int* v, unsigned n, unsigned state) {
  int old_end = v[n - 1];
  unsigned pivot = state < 2 || v[state - 2] > v[state] ? state - 1 : state - 2;
  int new_end = v[pivot];
  for (; pivot < n - 1; ++pivot) v[pivot] = v[pivot + 1];
  v[pivot] = new_end;
  return new_end < old_end ? n - 1 : state - 1;
}

如果注释不清楚，您可以使用以下代码来生成一副 4*k 牌的所有洗牌，而不考虑花色:

unsigned n = 4 * k;
int v[n];
for (unsigned i = 0; i < k; ++i)
  for (unsigned j = 0; j < 4; ++j)
    v[4 * i + j] = i;

unsigned state = 1;
do {
  /* process the permutation */ 
} while ((state = multipermute_step(v, n, state);

实际上，尝试对 k == 8 执行此操作需要一段时间，因为有 32!/(4!)⁸ 可能的洗牌。大约为 2.39*10²⁴。但我确实在0.3秒内完成了16张牌的所有洗牌，我估计半小时内可以洗完20张牌。