Can you write a permutation function just as elegantly in C#?

Question

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

Answer 1

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).

Answer 2

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.

Answer 3

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).

Answer 4

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