CODEWITHSUNDEEP
c#arraysalgorithmlinqpermutation
JCarter
JCarter

Reputation: 267

Permutations of numbers in array

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]:

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

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?

Upvotes: 3

Views: 5678

Answers (2)

Yacoub Massad
Yacoub Massad

Reputation: 27861

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.

Upvotes: 1

Mr.Riply
Mr.Riply

Reputation: 845

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

Upvotes: 0

Related Questions