Generating permutations of a set - efficiently and with distinction

Question

I'm building on code from here. I'd like to generate all permutations of a set, for example (taken from the thread):

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

There are possible permutations for every set, but this is not what I'd like to achieve. Take, for consideration, following set:

This would yield permutations, an extreme amout of . This would take an extraordinary long time to compute, as each zero is being considered unique.

Rather than that, I'd like to only generate distinct permutations. If we do that, there are only

permutations remaining, as 18 items are identical (k).

Now, I could run the code from the mentioned thread and store the results in a HashSet, eliminating the duplicate permutations. However, that would be extremely inefficient. I'm looking for an algorithm to generate permutations with distinction directly.

Answer 1

This is so far the best solution I've come up with. Suggestions for optimization welcome. It returns exactly n!/k! items.

It takes about one second to permute { 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;
    }
}

Answer 2

With Swap algorithm to find permutations you can directly exclude the parts that produce duplicate permutations. This algorithm is available on internet and you can find more information about it.

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;
}

Here is the image that shows how swap algorithm works.

So you have {A,B,C}, {A,C,B}, {B,A,C}, {B,C,A}, {C,B,A}, {C,A,B}

Now Consider A and B are equal. Ive edited the image with photoshop (sorry if im terrible at it!) And replaced B with A. As you can see in the image

Ive identified duplicates in image. If you skip them you will have {A,A,C}, {A,C,A}, {C,A,A}

You have to store items that are swapped so if the items are equal and we already had that swap we just skip to prevent dupes

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.

For test if you delete this part then this algorithm will produce duplicate permutations and console will output n!.

Answer 3

I have done this problem before. You just need to sort the array first and then use a boolean[] visited array to mark elements which you have visited. My solution using backtracking, in 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

Let's try it:

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}
   >  > = = = = = = = = = = = = = = = = =

Oops, there is no index j such that a[j] < a[j + 1]. But since we want all distinct permutations, we can sort each array and guarantee we start at the beginning:

{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}

Let's do a few more:

{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}
...

As you can see, the large elements are steadily (and distinctly) moving left until:

{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}

And ends without duplicating permutations.