I like this 6 line solution a lot and am trying to replicate it in C#. Basically, it permutes the elements of an array:
def permute(xs, pre=[]):
if len(xs) == 0:
yield pre
for i, x in enumerate(xs):
for y in permute(xs[:i] + xs[i+1:], pre + [x]):
yield y
Well, it probably isn't how I'd write it, but:
static IEnumerable<T[]> Permute<T>(this T[] xs, params T[] pre) {
if (xs.Length == 0) yield return pre;
for (int i = 0; i < xs.Length; i++) {
foreach (T[] y in Permute(xs.Take(i).Union(xs.Skip(i+1)).ToArray(), pre.Union(new[] { xs[i] }).ToArray())) {
yield return y;
}
}
}
Re your comment; I'm not entirely clear on the question; if you mean "why is this useful?" - among other things, there are a range of brute-force scenarios where you would want to try different permutations - for example, for small ordering problems like travelling sales person (that aren't big enough to warrant a more sophisticated solution), you might want to check whether it is best to go {base,A,B,C,base}, {base,A,C,B,base},{base,B,A,C,base}, etc.
If you mean "how would I use this method?" - untested, but something like:
int[] values = {1,2,3};
foreach(int[] perm in values.Permute()) {
WriteArray(perm);
}
void WriteArray<T>(T[] values) {
StringBuilder sb = new StringBuilder();
foreach(T value in values) {
sb.Append(value).Append(", ");
}
Console.WriteLine(sb);
}
If you mean "how does it work?" - iterator blocks (yield return) are a complex subject in themselves - Jon has a free chapter (6) in his book, though. The rest of the code is very much like your original question - just using LINQ to provide the moral equivalent of + (for arrays).
C# has a yield keyword that I imagine works pretty much the same as what your python code is doing, so it shouldn't be too hard to get a mostly direct translation.
However this is a recursive solution, so for all it's brevity it's sub-optimal. I don't personally understand all the math involved, but for good efficient mathematical permutations you want to use factoradics. This article should help:
http://msdn.microsoft.com/en-us/library/aa302371.aspx
[Update]: The other answer brings up a good point: if you're just using permutations to do a shuffle there are still better options available. Specifically, the Knuth/Fisher-Yates shuffle.
While you cannot port it while maintaining the brevity, you can get pretty close.
public static class IEnumerableExtensions
{
public static IEnumerable<IEnumerable<T>> Permutations<T>(this IEnumerable<T> source)
{
if (source == null)
throw new ArgumentNullException("source");
return PermutationsImpl(source, new T[0]);
}
private static IEnumerable<IEnumerable<T>> PermutationsImpl<T>(IEnumerable<T> source, IEnumerable<T> prefix)
{
if (source.Count() == 0)
yield return prefix;
foreach (var x in source)
foreach (var permutation in PermutationsImpl(source.Except(new T[] { x }),
prefix.Union(new T[] { x }))))
yield return permutation;
}
}
Not entirely to the point I must admit after some comments, but the code below can be used to generate a random permutation of a finite sequence. It's a variation of the Fisher-Yates shuffle algorithm. The example uses a sequence of int's but you can use any Enumerable<T> of course.
var ints = Enumerable.Range(0, 51);
var shuffledInts = ints.OrderBy(a => Guid.NewGuid());
You order by a random value (in this case a Guid) which essentially permutates your list. Whether NewGuid is a good source of randomness is debatable, but it's an elegant and compact solution (albeit for another problem then the question was actually about).
Taken from Jeff Atwood (Coding Horror).
