permutation in c#

Is it possible to generate all 开发者_运维技巧permutations of a collection in c#?

char[] inputSet = { 'A','B','C' };
Permutations<char> permutations = new Permutations<char>(inputSet);
foreach (IList<char> p in permutations)
{
   Console.WriteLine(String.Format("{{{0} {1} {2}}}", p[0], p[1], p[2]));
}

---

I've already faced the problem and I wrote these simple methods:

    public static IList<T[]> GeneratePermutations<T>(T[] objs, long? limit)
    {
        var result = new List<T[]>();
        long n = Factorial(objs.Length);
        n = (!limit.HasValue || limit.Value > n) ? n : (limit.Value);

        for (long k = 0; k < n; k++)
        {
            T[] kperm = GenerateKthPermutation<T>(k, objs);
            result.Add(kperm);
        }

        return result;
    }

    public static T[] GenerateKthPermutation<T>(long k, T[] objs)
    {
        T[] permutedObjs = new T[objs.Length];

        for (int i = 0; i < objs.Length; i++)
        {
            permutedObjs[i] = objs[i];
        }
        for (int j = 2; j < objs.Length + 1; j++)
        {
            k = k / (j - 1);                      // integer division cuts off the remainder
            long i1 = (k % j);
            long i2 = j - 1;
            if (i1 != i2)
            {
                T tmpObj1 = permutedObjs[i1];
                T tmpObj2 = permutedObjs[i2];
                permutedObjs[i1] = tmpObj2;
                permutedObjs[i2] = tmpObj1;
            }
        }
        return permutedObjs;
    }

    public static long Factorial(int n)
    {
        if (n < 0) { throw new Exception("Unaccepted input for factorial"); }    //error result - undefined
        if (n > 256) { throw new Exception("Input too big for factorial"); }  //error result - input is too big

        if (n == 0) { return 1; }

        // Calculate the factorial iteratively rather than recursively:

        long tempResult = 1;
        for (int i = 1; i <= n; i++)
        {
            tempResult *= i;
        }
        return tempResult;
    }

Usage:

var perms = Utilities.GeneratePermutations<char>(new char[]{'A','B','C'}, null);

---

There's nothing built in.

I've found a a couple of Code Project articles here and here which might help you implement your own class.

---

    public static void Recursion(char[] charList, int loBound, int upBound )
    {
            for (int i = loBound; i <= upBound; i++)
            {

                swap(ref charList[loBound], ref charList[i]);
                if (loBound == upBound)
                {
                    Console.Write(charList);
                    Console.WriteLine("");
                }

                Recursion(charList, loBound + 1, upBound);
                swap(ref charList[loBound], ref charList[i]);
            }

        }



    public static void swap(ref char a, ref char b)
    {
        if (a == b) return;
        a ^= b;
        b ^= a;
        a ^= b;
    }

    public static void Main(string[] args)
    {
        string c = "123";
        char[] c2 = c.ToCharArray();
        Recursion(c2, 0, c2.Length-1);
        Console.ReadKey();
    }

---

I built these Extensions Methods for Enumerable<T>

The following Generics Methods can find Permutations as well as Combinations of an IEnumerable of any type. Visit http://github.com/MathewSachin/Equamatics for more

using System;
using System.Collections.Generic;
using System.Linq;

namespace Equamatics
{
public static class Combinatorics
{
    #region Permute
    public static IEnumerable<IEnumerable<T>> Permute<T>(this IEnumerable<T> Input, int r = -1)
    {
        int n = Input.Count();

        if (r == -1) foreach (var item in new Permutor<T>(Input).Recursion(0))
                yield return item;

        if (r > n) throw new ArgumentOutOfRangeException("r cannot be greater than no of elements");

        foreach (var list in Input.Combinations(r))
            foreach (var item in new Permutor<T>(list).Recursion(0))
                yield return item;
    }

    class Permutor<T>
    {
        int ElementLevel = -1;
        int[] PermutationValue;
        T[] Elements;

        public Permutor(IEnumerable<T> Input)
        {
            Elements = Input.ToArray();

            PermutationValue = new int[Input.Count()];
        }

        public IEnumerable<IEnumerable<T>> Recursion(int k)
        {
            ElementLevel++;
            PermutationValue[k] = ElementLevel;

            if (ElementLevel == Elements.Length)
            {
                List<T> t = new List<T>();

                foreach (int i in PermutationValue) t.Add(Elements[i - 1]);

                yield return t;
            }
            else
                for (int i = 0; i < Elements.Length; i++)
                    if (PermutationValue[i] == 0)
                        foreach (IEnumerable<T> e in Recursion(i))
                            yield return e;

            ElementLevel--;
            PermutationValue[k] = 0;
        }
    }

    public static double P(int n, int r)
    {
        if (r < 0 | n < 0 | n < r) return Double.NaN;
        else if (r == 0) return 1;
        else if (n == r) return Factorial(n);
        else
        {
            double Product = 1;
            for (int i = n - r + 1; i <= n; ++i) Product *= i;
            return Product;
        }
    }
    #endregion

    #region Combinations
    public static IEnumerable<IEnumerable<T>> Combinations<T>(this IEnumerable<T> Input, int r = -1)
    {            
        if (r == -1)
        {
            yield return Input;
            yield break;
        }

        int n = Input.Count();

        if (r > n) throw new ArgumentOutOfRangeException("r cannot be greater than no of elements");

        int[] Indices = Enumerable.Range(0, r).ToArray();

        yield return Indices.Select(k => Input.ElementAt(k));

        while (true)
        {
            int i;
            for (i = r - 1; i >= 0; --i)
                if (Indices[i] != i + n - r)
                    break;

            if (i < 0) break;

            Indices[i] += 1;

            for (int j = i + 1; j < r; ++j)
                Indices[j] = Indices[j - 1] + 1;
            yield return Indices.Select(k => Input.ElementAt(k));
        }
    }

    public static double C(int n, int r)
    {
        if (r < 0 | n < 0 | n < r) return Double.NaN;
        else if (n - r == 1 | r == 1) return n;
        else if (n == r | r == 0) return 1;
        else if (n - r > r) return (P(n, n - r) / Factorial(n - r));
        else return (P(n, r) / Factorial(r));
    }
    #endregion

    public static double Factorial(int n)
    {
        if (n < 0) return Double.NaN;
        else if (n == 0) return 1;
        else
        {
            double Product = 1;
            for (int i = 1; i <= n; ++i) Product *= i;
            return Product;
        }
    }

    public static int Derangement(int n)
    {
        double x = 0;
        for (int i = 2; i <= n; ++i)
        {
            if (i % 2 == 0) x += (1 / Factorial(i));
            else x -= (1 / Factorial(i));
        }
        return (int)(Factorial(n) * x);
    }

    public static int Catalan(int n) { return (int)C(2 * n, n) / (n + 1); }
}
}

`

---

A simple implementation using recursion

    static void Main(string[] args)
    {
        char[] inputSet = { 'A', 'B', 'C' };
        var permutations = GetPermutations(new string(inputSet));
        foreach (var p in permutations)
        {
            Console.WriteLine(String.Format("{{{0} {1} {2}}}", p[0], p[1], p[2]));
        }
    }

    public static List<string> GetPermutations(string str)
    {
        List<string> result = new List<string>();

        if (str == null)
            return null;

        if (str.Length == 0)
        {
            result.Add("");
            return result;
        }

        char c = str.ElementAt(0);
        var perms = GetPermutations(str.Substring(1));

        foreach (var word in perms)
        {
            for (int i = 0; i <= word.Length; i++)
            {
                result.Add(word.Substring(0, i) + c + word.Substring(i));
            }
        }

        return result;
    }