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

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