¿Se puede escribir una función de permutación tan elegantemente en C#?

Question

Me gusta mucho esta solución de 6 líneas y estoy tratando de replicarla en C#. Básicamente, se permuta los elementos de una matriz:

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

Bueno, probablemente no es la forma en que me gustaría escribir, pero:

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 su comentario; No soy completamente claro en la pregunta; si quieres decir "¿por qué es esto útil?" - entre otras cosas, hay una variedad de escenarios de fuerza bruta en los que desearía probar diferentes permutaciones; por ejemplo, para pequeños problemas de pedidos, como vendedores ambulantes (que no son lo suficientemente grandes como para justificar una solución más sofisticada), usted podría querer comprobar si es mejor ir {base, A, B, C, base}, {base, A, C, B, base}, {base, B, A, C, base}, etc.

Si quiere decir "¿cómo usaría este método?" - no probado, pero algo así como:

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

Si quiere decir "¿cómo funciona?" - Los bloques de iterador (yield return) son un tema complejo en sí mismos. Sin embargo, Jon tiene un capítulo libre (6) in his book. El resto del código es muy parecido a su pregunta original, simplemente usando LINQ para proporcionar el equivalente moral de + (para matrices).

Answer 2

No del todo hasta el punto debo admitir que después de algunos comentarios, pero el código siguiente puede utilizarse para generar una permutación aleatoria de una secuencia finita. Es una variación del Fisher-Yates shuffle algorithm. El ejemplo usa una secuencia de int, pero puede usar cualquier Enumerable<T>, por supuesto.

var ints = Enumerable.Range(0, 51); 
var shuffledInts = ints.OrderBy(a => Guid.NewGuid()); 

hace su pedido por un valor aleatorio (en este caso un Guid), que esencialmente permutates su lista. Si el NewGuid es una buena fuente de aleatoriedad es discutible, pero es una solución elegante y compacta (aunque para otro problema, la pregunta en realidad se trataba).

Tomado de Jeff Atwood (Coding Horror).

Answer 3

C# tiene una clave de rendimiento que me imagino que funciona prácticamente igual a lo que está haciendo su código python, por lo que no debería ser demasiado difícil obtener una traducción principalmente directa.

Sin embargo, esta es una solución recursiva, por lo que para su brevedad no es óptima. Personalmente no entiendo todas las matemáticas involucradas, pero para las permutaciones matemáticas buenas y eficientes quiero usar factoradics. Este artículo debería ayudar:
http://msdn.microsoft.com/en-us/library/aa302371.aspx

[Actualización]: La otra respuesta nos lleva a un buen punto: si sólo está utilizando permutaciones hacer una reproducción aleatoria todavía hay mejores opciones disponibles. Específicamente, el Knuth/Fisher-Yatesshuffle.

Answer 4

Si bien no puede portarlo manteniendo la brevedad, puede acercarse bastante.

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