algorithm - 列出一组给定值的所有排列

Question

我对比较可用于生成给定集合的所有潜在排列的不同技术/方法很感兴趣。

Answer 1

您可以在性能、特定分布和简单性之间进行选择。我所说的特定分布是指您是否关心输出的某些特定顺序，例如字典顺序。

据我所知，性能最好的算法是 Steinhaus algorithm .它是乘法常数的最佳选择，因为生成一个排列只需要恒定数量的处理器指令(不计算打印它并不总是需要的指令)。

还有一个非常简单的算法可以生成字典顺序的排列，您可以自己将其重新发明为递归过程，其性能为 O(n.log(n).log( n))，因此与通过任何其他方法生成列表并对其进行排序大致相同。

编辑:这里是简单算法的伪代码:

void permute(Element[] permutationPrefix, Set rest)
{
    if (rest.IsEmpty) {
        // permutationPrefix is now a full permutation
        print(permutationPrefix);
    } else {
        foreach (element in rest) {
            permutationPrefix.Append(element);
            permute(permutationPrefix, rest.Minus(element))
            permutationPrefix.Length--;  // cut away the last item
        }
    }
}

最初用一个空的 permutationPrefix 和保存完整集合的 rest 来调用它；如果这个集合是一个排序的数据结构，排列将按字典顺序输出。

请注意，我们在每次递归调用时复制和修改集合，这是整个算法中成本最高的操作，可能与 print 方法一起使用。单个集合副本的成本与排列总数n成对数；并且因为递归调用堆栈的深度也是对数的，O(n.log(n).log(n)) 性能估计如下。

(该算法也适用于转换为性能良好的随机排列生成器。)