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

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}

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

这将产生 permutations, an extreme amout of 。这将花费非常长的时间来计算，因为每个零都被认为是唯一的。

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

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

Answer 2

让我们试试看：

Knuths
1. Find the largest index j such that a[j] < a[j + 1]. If no
such index exists, the permutation is the last permutation.

{20,10,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}
   >  > = = = = = = = = = = = = = = = = =

糟糕，没有满足 a[j] < a[j + 1] 的索引 j。但是由于我们想要 all 个不同的排列，我们可以对每个数组进行排序并保证我们从头开始：

{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,10,20}

1. Find the largest index j such that a[j] < a[j + 1]. If no
such index exists, the permutation is the last permutation.

j = 18 since a[18] < a[19]

2. Find the largest index l such that a[j] < a[l]. Since j + 1
is such an index, l is well defined and satisfies j < l.

l = 19 since a[18] < a[19]

3. Swap a[j] with a[l].

{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,20,10}

4. Reverse the sequence from a[j + 1] up to and including the final element a[n].

{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,20,10}

让我们再做一些：

{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,20,10}
yields {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,10,0,20}
yields {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,10,20,0}
yields {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,20,0,10}
yields {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,20,10,0}
yields {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,10,0,0,20}
...

如您所见，大元素稳定地（明显地）向左移动，直到：

{10,20,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}
yields {20,10,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}

并在不重复排列的情况下结束。

Answer 3

这道题我以前做过。您只需要先对数组进行排序，然后使用 boolean[] visited 数组来标记您访问过的元素。我在 Java 中使用回溯的解决方案：

public class Solution {
    public List<List<Integer>> permuteUnique(int[] num) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        List<Integer> list = new ArrayList<Integer>();
        boolean[] visited = new boolean[num.length];

        Arrays.sort(num);
        helper(result, list, num, visited);

        return result;
    }

    private void helper(List<List<Integer>> result, List<Integer> list,
            int[] num, boolean[] visited) {
        for (int i = 0; i < num.length; i++) {
            if (visited[i]
                    || (i > 0 && num[i] == num[i - 1] && !visited[i - 1])) {
                continue;
            }
            list.add(num[i]);
            visited[i] = true;
            if (list.size() == num.length) {
                result.add(new ArrayList<Integer>(list));
            } else {
                helper(result, list, num, visited);
            }
            list.remove(list.size() - 1);
            visited[i] = false;
        }
    }
}

Answer 4

这是迄今为止我想到的最好的解决方案。欢迎提出优化建议。它returns正好是n!/k!项目。

置换大约需要一秒钟 { 20, 4, 3, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 , 0 }.

private static IEnumerable<int[]> Permute(int[] list)
{
    if (list.Length > 1)
    {    
        int n = list[0];
        foreach (int[] subPermute in Permute(list.Skip(1).ToArray()))
        {    
            for (int index = 0; index <= subPermute.Length; index++)
            {
                int[] pre = subPermute.Take(index).ToArray();
                int[] post = subPermute.Skip(index).ToArray();

                if (post.Contains(n))
                    continue;

                yield return pre.Concat(new[] { n }).Concat(post).ToArray();
            }    
        }
    }
    else
    {
        yield return list;
    }
}

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

Generating permutations of a set - efficiently and with distinction

c#

algorithm

recursion

performance

permutation