我想生成32副牌组的所有排列，我将牌表示为数字0-7，所以我不在乎牌的颜色。游戏很简单(把牌组分成两张，比较两张牌，把两张牌都加到一组更大的牌中(。我已经对游戏的这一部分进行了编码，但现在牌组是随机生成的，我想看看牌的所有可能性，并对其进行一些统计。我如何对这张牌的生成进行编码？我完全不知道如何编码。
因为我刚刚在研究Aaron Williams 2009年的论文《通过前缀移位的多集置换的无环生成》，我将贡献他的算法的一个版本，它正好解决了这个问题。我相信它比通常被引用的标准C++next_permutation更快，因为它不依赖于搜索输入向量的轴心点。但需要更广泛的基准测试才能得出明确的答案；很有可能它最终会移动更多的数据。
Williams算法的实现通过将排列存储在链表中来避免数据移动，这允许"前缀移位"(将向量的前缀旋转一个位置(只需修改两个next指针即可实现。这使得算法无环。
我的版本在几个方面有所不同。
-
首先，它使用一个普通数组来存储值，这意味着移位确实需要一个循环。另一方面，它避免了必须实现链表数据类型，并且许多操作在数组上更快。
-
其次，它使用后缀移位而不是前缀移位；实际上，它产生了每个排列的相反(与Williams的实现相比(。我这么做是因为它简化了对启动条件的描述。
-
最后，它只执行一个置换步骤。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！(8可能的混洗。这大约是2.39*1024。但我确实在0.3秒内完成了16张牌的所有洗牌，我估计我可以在半小时内完成20张牌。