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);
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;
}
Permutationsis your own class.Permuatationsclass already exists rather than having to write it.