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

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

From stackoverflow

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

  Adam Robinson : How does this perform any permutations...?

  Ronald Wildenberg : If you order by a random value (a Guid in this case), you essentially permutate your list.

  Samuel : @rwwilden: No you don't. http://en.wikipedia.org/wiki/Permutation

  Lucas : @rwwilden: permute != shuffle

  Joel Coehoorn : shuffles are like a special case of a permutation, in that you can use permutations to shuffle accurately (if more slowly than with a specialized algorithm). Even the wikipedia article above mentions Fisher-Yates as "based on the same principle".

  Joel Coehoorn : Even so, ordering by a new guid is not the best idea, and while all shuffles are permutations, not all permutations are good shuffles.

  Ronald Wildenberg : After reading up on permutations I see that I have answered this one incorrect, sorry for that. However, the method described is a good way for generating random permutations of a finite set, although not as fast as possible (and the source of randomness is debatable). Updated my answer.

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

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

  Marc Gravell : Well, it would involve less LINQ, and probably two methods (one for the public caller, one separate for recursion), and a re-used buffer. Or I'd look at the links in the other post ;-p

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

  Marc Gravell : The approach with Equals makes it hazardous for anything with either duplicates or nulls.

  Samuel : Regular permutations don't take duplicates (should be checked), but you are right about nulls.