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

Question

我正在建立代码来自这里.我想生成一组的所有排列,例如(取自线程):

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

有 每组的可能排列,但这不是我想要实现的.考虑以下集合:

这会产生 排列,极端的 .这需要非常长的时间来计算,因为每个零被认为是唯一的.

而不是那样,我只想产生不同的排列.如果我们这样做,那就是

剩下的排列,因为18项是相同的(k).

现在,我可以运行上述线程中的代码并将结果存储在HashSet中,从而消除了重复的排列.但是,这将是非常低效的.我正在寻找一种算法来直接生成具有区别的排列.

Answer 1

使用Swap算法查找排列,您可以直接排除产生重复排列的部分.此算法可在互联网上获得,您可以找到有关它的更多信息.

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!.