how to find all permutations in an array [duplicate]
What is the best way to find all combinations of items in an array in c#?
Solution 1:
UPDATED
Here are a set of generic functions (require .net 3.5 or higher) for different scenarios. The outputs are for a list of {1, 2, 3, 4} and a length of 2.
Permutations with repetition
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 }));
}
Output:
{1,1} {1,2} {1,3} {1,4} {2,1} {2,2} {2,3} {2,4} {3,1} {3,2} {3,3} {3,4} {4,1} {4,2} {4,3} {4,4}
Permutations
static IEnumerable<IEnumerable<T>>
GetPermutations<T>(IEnumerable<T> list, int length)
{
if (length == 1) return list.Select(t => new T[] { t });
return GetPermutations(list, length - 1)
.SelectMany(t => list.Where(o => !t.Contains(o)),
(t1, t2) => t1.Concat(new T[] { t2 }));
}
Output:
{1,2} {1,3} {1,4} {2,1} {2,3} {2,4} {3,1} {3,2} {3,4} {4,1} {4,2} {4,3}
K-combinations with repetition
static IEnumerable<IEnumerable<T>>
GetKCombsWithRept<T>(IEnumerable<T> list, int length) where T : IComparable
{
if (length == 1) return list.Select(t => new T[] { t });
return GetKCombsWithRept(list, length - 1)
.SelectMany(t => list.Where(o => o.CompareTo(t.Last()) >= 0),
(t1, t2) => t1.Concat(new T[] { t2 }));
}
Output:
{1,1} {1,2} {1,3} {1,4} {2,2} {2,3} {2,4} {3,3} {3,4} {4,4}
K-combinations
static IEnumerable<IEnumerable<T>>
GetKCombs<T>(IEnumerable<T> list, int length) where T : IComparable
{
if (length == 1) return list.Select(t => new T[] { t });
return GetKCombs(list, length - 1)
.SelectMany(t => list.Where(o => o.CompareTo(t.Last()) > 0),
(t1, t2) => t1.Concat(new T[] { t2 }));
}
Output:
{1,2} {1,3} {1,4} {2,3} {2,4} {3,4}
Solution 2:
That's called permutations.
This can give you the permutations of any collection:
public class Permutation {
public static IEnumerable<T[]> GetPermutations<T>(T[] items) {
int[] work = new int[items.Length];
for (int i = 0; i < work.Length; i++) {
work[i] = i;
}
foreach (int[] index in GetIntPermutations(work, 0, work.Length)) {
T[] result = new T[index.Length];
for (int i = 0; i < index.Length; i++) result[i] = items[index[i]];
yield return result;
}
}
public static IEnumerable<int[]> GetIntPermutations(int[] index, int offset, int len) {
if (len == 1) {
yield return index;
} else if (len == 2) {
yield return index;
Swap(index, offset, offset + 1);
yield return index;
Swap(index, offset, offset + 1);
} else {
foreach (int[] result in GetIntPermutations(index, offset + 1, len - 1)) {
yield return result;
}
for (int i = 1; i < len; i++) {
Swap(index, offset, offset + i);
foreach (int[] result in GetIntPermutations(index, offset + 1, len - 1)) {
yield return result;
}
Swap(index, offset, offset + i);
}
}
}
private static void Swap(int[] index, int offset1, int offset2) {
int temp = index[offset1];
index[offset1] = index[offset2];
index[offset2] = temp;
}
}
Example:
string[] items = { "one", "two", "three" };
foreach (string[] permutation in Permutation.GetPermutations<string>(items)) {
Console.WriteLine(String.Join(", ", permutation));
}