Permutations of numbers in array

Question

I'd like to get all possible permutations of numbers in an array - n!/k! whereas n is the size of the array and k the number of identical numbers.

For example, there would be 3 (3!/2!) possible permutations of [3,0,0]:

[3,0,0]
[0,3,0]
[0,0,3]

Another example would be [2,1,0], which would yield 6 (3!/1!) permutations:

[2,1,0]
[1,2,0]
[0,1,2]
[0,2,1]
[2,0,1]
[1,0,2]

I've been successfully using code from here:

static IEnumerable<IEnumerable<T>> 
    GetPermutationsWithRept<T>(IEnumerable<T> list, int length)
{
    if (length == 1) return list.Select(t => new T[] { t });
    return GetPermutationsWithRept(list, length - 1)
        .SelectMany(t => list, 
            (t1, t2) => t1.Concat(new T[] { t2 }));
}

After generating the permutations, I would run Sum() to validate each permutation. This, however, might not be a efficient solution. Is there another way to achieve this?

How about [this](https://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order)? — user4003407, Oct 23 '15 at 22:52
@AhmadHammoud because apparently OP does not trust solution provided in other answer (fair, but careful review of code would be better to verify if code is correct)... Not really sure what OP is looking for. — Alexei Levenkov, Oct 23 '15 at 22:54
@AhmadHammoud The code above would return 27 permutations for [3,0,0], including ones such as [3,3,3,], [3,3,0] etc. What I kind of desire is all possible outcomes when you "shuffle" the array. — JCarter, Oct 23 '15 at 23:19

score 1 · Answer 1 · answered Oct 24 '15 at 00:55

Using Sum to filter the output of GetPermutationsWithRept is not correct. Consider this case:

{1,2,3}

One of the outputs of GetPermutationsWithRept in this case would be {2,2,2}. The sums are equal (2+2+2 = 1+2+3). However, {2,2,2} is not a valid output.

Here is a solution that builds on your method:

This class is used to compare output items (to calculate distinct results):

public class EnumerableComparer<T> : IEqualityComparer<IEnumerable<T>>
{
    public bool Equals(IEnumerable<T> x, IEnumerable<T> y)
    {
        return x.SequenceEqual(y);
    }

    public int GetHashCode(IEnumerable<T> obj)
    {
        return string.Join("-", obj.Select(x => x.ToString())).GetHashCode();
    }
}

The following code calls the GetPermutationsWithRept, and filters the results two times. The first time to remove invalid items like {3,3,3} ad {2,2,2}, and the second time to remove duplicates.

var list = new int[] {1, 2, 3};

var result1 = GetPermutationsWithRept(list, 3).ToList();

var sorted_list = list.OrderBy(item => item).ToList();

var result2 = result1
    .Where(rlist => rlist.OrderBy(x => x).SequenceEqual(sorted_list)) //first filter
    .Distinct(new EnumerableComparer<int>()) //second filter
    .ToList();

I think that in terms of performance, this solution wouldn't be great for large inputs, but it is correct.

score 0 · Answer 2 · answered Oct 23 '15 at 23:25

The function takes a string of characters, and writes down every possible permutation of that exact string, so for example, if "ABC" has been supplied, should spill out:

ABC, ACB, BAC, BCA, CAB, CBA.

Code:

class Program
{
    private static void Swap(ref char a, ref char b)
    {
        if (a == b) return;

        a ^= b;
        b ^= a;
        a ^= b;
    }

    public static void GetPer(char[] list)
    {
        int x = list.Length - 1;
        GetPer(list, 0, x);
    }

    private static void GetPer(char[] list, int k, int m)
    {
        if (k == m)
        {
        Console.Write(list);
        }
        else
            for (int i = k; i <= m; i++)
            {
                   Swap(ref list[k], ref list[i]);
                   GetPer(list, k + 1, m);
                   Swap(ref list[k], ref list[i]);
            }
    }

    static void Main()
    {
        string str = "abc";
        char[] arr = str.ToCharArray();
        GetPer(arr);
    }
}

Permutations of numbers in array

2 Answers2