c# - 生成集合的排列 - 高效且有区别

Question

我正在构建来自 here 的代码.我想生成一个集合的所有排列，例如(取自线程):

Collection: 1, 2, 3
Permutations: {1, 2, 3}
              {1, 3, 2}
              {2, 1, 3}
              {2, 3, 1}
              {3, 1, 2}
              {3, 2, 1}

有每个集合的可能排列，但这不是我想要实现的。考虑以下集合:

这将产生 排列，极端数量 .这将花费非常长的时间来计算，因为每个零都被认为是唯一的。

除此之外，我只想生成不同的排列。如果我们这样做，只有

排列 remaining , 因为有 18 个项目是相同的 (k)。

现在，我可以运行上述线程中的代码并将结果存储在 HashSet 中，从而消除重复排列。然而，那将是极其低效的。我正在寻找一种算法来直接生成有区别的排列。

Answer 1

使用Swap算法寻找排列可以直接排除产生重复排列的部分。该算法可在 Internet 上找到，您可以找到有关它的更多信息。

private static void Main(string[] args)
{
    List<int> set = new List<int>
    {
        20, 4, 3, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
    };
    var permutes = Permute(set);

    Console.WriteLine(permutes.Count); // outputs 58140
}

private static List<int[]> Permute(List<int> set)
{
    List<int[]> result = new List<int[]>(); 

    Action<int> permute = null;
    permute = start =>
    {
        if (start == set.Count)
        {
            result.Add(set.ToArray());
        }
        else
        {
            List<int> swaps = new List<int>();
            for (int i = start; i < set.Count; i++)
            {
                if (swaps.Contains(set[i])) continue; // skip if we already done swap with this item
                swaps.Add(set[i]);

                Swap(set, start, i);
                permute(start + 1); 
                Swap(set, start, i);
            }
        }
    };

    permute(0);

    return result;
}

private static void Swap(List<int> set, int index1, int index2)
{
    int temp = set[index1];
    set[index1] = set[index2];
    set[index2] = temp;
}

下图展示了交换算法的工作原理。

所以你有 {A,B,C}, {A,C,B}, {B,A,C}, {B,C,A}, {C,B,A}, { C,A,B}

现在考虑 A 和 B 相等。我用 photoshop 编辑了图像(对不起，如果我不擅长它!)并将 B 替换为 A。如图所示

我发现了图像中的重复项。如果你跳过它们，你将得到 {A,A,C}, {A,C,A}, {C,A,A}

你必须存储交换的项目，所以如果项目相等并且我们已经进行了交换，我们就跳过以防止重复

if (swaps.Contains(set[i])) continue; // skip if we already done swap with this item
swaps.Add(set[i]); // else add it to the list of swaps.

为了测试如果你删除这部分那么这个算法会产生重复的排列并且控制台会输出n!。