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.

I'm confused. The code in the linked thread is doing a lexicographic increment, which actually works fine on multisets with duplicate elements, no HashSet required. — David Eisenstat, Oct 25 '15 at 11:33
Well I would say that all you need to do is use distinct subset of the input before applying the algorithm. — Zdeněk Jelínek, Oct 25 '15 at 11:34
@DavidEisenstat It works fine, but it takes a long time to compute. If I don't use the HashSet, I would have 2.4 * 10^18 results. — jacobz, Oct 25 '15 at 11:38
No, I mean that the generated permutations are pairwise distinct. — David Eisenstat, Oct 25 '15 at 11:40

M.kazem Akhgary · Accepted Answer · 2015-10-25T15:22:21.083

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

I've tested this with Permute(new List() {20, 4, 3, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}), however it will trigger an OutOfMemoryException as list will grow over 10 million (the actual result should be 58410) — jacobz, Oct 25 '15 at 14:08
@Jacobus21 thanks for the information. ive fixed it by remembering swaps. test it now ;) — M.kazem Akhgary, Oct 25 '15 at 14:48
Wonderful! It takes about 28 seconds to permute { 20, 4, 3, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, which is two seconds faster than my method. Is there any way to further optimize it? — jacobz, Oct 25 '15 at 15:29
My bad, I was writing results into a list which slowed things down significantly. It's really fast! — jacobz, Oct 25 '15 at 16:30

jacobz · Answer 2 · 2015-10-25T16:28:20.130

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

Impressive! Thanks for including an approx time – D. Ben Knoble Oct 25 '15 at 18:55 — D. Ben Knoble, Oct 25 '15 at 18:55

score 1 · Answer 3 · answered Oct 25 '15 at 13:21

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.

score 1 · Answer 4 · answered Oct 25 '15 at 13:49

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

Generating permutations of a set - efficiently and with distinction

4 Answers4