¿Cómo calcularías todas las permutaciones posibles de 0 a N de forma iterativa?

Question

Necesito calcular permutaciones iterativamente. La firma del método se ve así:

int[][] permute(int n)

Para n = 3 por ejemplo, el valor de retorno sería:

[[0,1,2], 
[0,2,1], 
[1,0,2], 
[1,2,0], 
[2,0,1], 
[2,1,0]] 

Cómo haría usted para hacer esto de forma iterativa de la manera más eficiente posible? Puedo hacer esto recursivamente, pero estoy interesado en ver muchas formas alternativas de hacerlo iterativamente.

Answer 1

ver QuickPerm algoritmo, que es iterativo: http://www.quickperm.org/

Editar:

Reescrito en Ruby para mayor claridad:

def permute_map(n) 
    results = [] 
    a, p = (0...n).to_a, [0] * n 
    i, j = 0, 0 
    i = 1 
    results << yield(a) 
    while i < n 
    if p[i] < i 
     j = i % 2 * p[i] # If i is odd, then j = p[i], else j = 0 
     a[j], a[i] = a[i], a[j] # Swap 
     results << yield(a) 
     p[i] += 1 
     i = 1 
    else 
     p[i] = 0 
     i += 1 
    end 
    end 
    return results 
end 

Answer 2

He utilizado los algoritmos de here. La página contiene mucha información útil.

Editar: Lo siento, esos fueron recursivos. uray publicó el enlace al algoritmo iterativo en su respuesta.

He creado un ejemplo de PHP. A menos que realmente necesita para devolver todos los resultados, sólo crearía una clase iterativo como el siguiente:

<?php 
class Permutator implements Iterator 
{ 
    private $a, $n, $p, $i, $j, $k; 
    private $stop; 

    public function __construct(array $a) 
    { 
    $this->a = array_values($a); 
    $this->n = count($this->a); 
    } 

    public function current() 
    { 
    return $this->a; 
    } 

    public function next() 
    { 
    ++$this->k; 
    while ($this->i < $this->n) 
    { 
     if ($this->p[$this->i] < $this->i) 
     { 
     $this->j = ($this->i % 2) * $this->p[$this->i]; 

     $tmp = $this->a[$this->j]; 
     $this->a[$this->j] = $this->a[$this->i]; 
     $this->a[$this->i] = $tmp; 

     $this->p[$this->i]++; 
     $this->i = 1; 
     return; 
     } 

     $this->p[$this->i++] = 0; 
    } 

    $this->stop = true; 
    } 

    public function key() 
    { 
    return $this->k; 
    } 

    public function valid() 
    { 
    return !$this->stop; 
    } 

    public function rewind() 
    { 
    if ($this->n) $this->p = array_fill(0, $this->n, 0); 
    $this->stop = $this->n == 0; 
    $this->i = 1; 
    $this->j = 0; 
    $this->k = 0; 
    } 

} 

foreach (new Permutator(array(1,2,3,4,5)) as $permutation) 
{ 
    var_dump($permutation); 
} 
?> 

Nota que trata a cada matriz PHP en forma de matriz.

Answer 3

El algoritmo para pasar de una permutación a la siguiente es muy similar a la adición a la escuela primaria: cuando ocurre un desbordamiento, "transporta el que está".

Aquí es una implementación he escrito en C:

#include <stdio.h> 

//Convenience macro. Its function should be obvious. 
#define swap(a,b) do { \ 
     typeof(a) __tmp = (a); \ 
     (a) = (b); \ 
     (b) = __tmp; \ 
    } while(0) 

void perm_start(unsigned int n[], unsigned int count) { 
    unsigned int i; 
    for (i=0; i<count; i++) 
     n[i] = i; 
} 

//Returns 0 on wraparound 
int perm_next(unsigned int n[], unsigned int count) { 
    unsigned int tail, i, j; 

    if (count <= 1) 
     return 0; 

    /* Find all terms at the end that are in reverse order. 
     Example: 0 3 (5 4 2 1) (i becomes 2) */ 
    for (i=count-1; i>0 && n[i-1] >= n[i]; i--); 
    tail = i; 

    if (tail > 0) { 
     /* Find the last item from the tail set greater than 
      the last item from the head set, and swap them. 
      Example: 0 3* (5 4* 2 1) 
      Becomes: 0 4* (5 3* 2 1) */ 
     for (j=count-1; j>tail && n[j] <= n[tail-1]; j--); 

     swap(n[tail-1], n[j]); 
    } 

    /* Reverse the tail set's order */ 
    for (i=tail, j=count-1; i<j; i++, j--) 
     swap(n[i], n[j]); 

    /* If the entire list was in reverse order, tail will be zero. */ 
    return (tail != 0); 
} 

int main(void) 
{ 
    #define N 3 
    unsigned int perm[N]; 

    perm_start(perm, N); 
    do { 
     int i; 
     for (i = 0; i < N; i++) 
      printf("%d ", perm[i]); 
     printf("\n"); 
    } while (perm_next(perm, N)); 

    return 0; 
} 

Answer 4

Está usando 1.9's Matriz # permutación una opción?

>> a = [0,1,2].permutation(3).to_a 
=> [[0, 1, 2], [0, 2, 1], [1, 0, 2], [1, 2, 0], [2, 0, 1], [2, 1, 0]] 

Answer 5

Aquí es una implementación en C#, como un método de extensión:

public static IEnumerable<List<T>> Permute<T>(this IList<T> items) 
{ 
    var indexes = Enumerable.Range(0, items.Count).ToArray(); 

    yield return indexes.Select(idx => items[idx]).ToList(); 

    var weights = new int[items.Count]; 
    var idxUpper = 1; 
    while (idxUpper < items.Count) 
    { 
     if (weights[idxUpper] < idxUpper) 
     { 
      var idxLower = idxUpper % 2 * weights[idxUpper]; 
      var tmp = indexes[idxLower]; 
      indexes[idxLower] = indexes[idxUpper]; 
      indexes[idxUpper] = tmp; 
      yield return indexes.Select(idx => items[idx]).ToList(); 
      weights[idxUpper]++; 
      idxUpper = 1; 
     } 
     else 
     { 
      weights[idxUpper] = 0; 
      idxUpper++; 
     } 
    } 
} 

Y una prueba de unidad:

[TestMethod] 
public void Permute() 
{ 
    var ints = new[] { 1, 2, 3 }; 
    var orderings = ints.Permute().ToList(); 
    Assert.AreEqual(6, orderings.Count); 
    AssertUtil.SequencesAreEqual(new[] { 1, 2, 3 }, orderings[0]); 
    AssertUtil.SequencesAreEqual(new[] { 2, 1, 3 }, orderings[1]); 
    AssertUtil.SequencesAreEqual(new[] { 3, 1, 2 }, orderings[2]); 
    AssertUtil.SequencesAreEqual(new[] { 1, 3, 2 }, orderings[3]); 
    AssertUtil.SequencesAreEqual(new[] { 2, 3, 1 }, orderings[4]); 
    AssertUtil.SequencesAreEqual(new[] { 3, 2, 1 }, orderings[5]); 
} 

El método AssertUtil.SequencesAreEqual es un ayudante de prueba personalizada que se pueden volver a crear fácilmente suficiente.

Answer 6

abajo es mi genéricos versión de la siguiente algoritmo de permutación en C# se parece mucho a la función next_permutation del STL (pero no revierte la colección si es la permutación máximo posible ya, al igual que la versión C++ hace)

En teoría, debería funcionar con cualquier IList <> de IComparables.

static bool NextPermutation<T>(IList<T> a) where T: IComparable 
    { 
     if (a.Count < 2) return false; 
     var k = a.Count-2; 

     while (k >= 0 && a[k].CompareTo(a[k+1]) >=0) k--; 
     if(k<0)return false; 

     var l = a.Count - 1; 
     while (l > k && a[l].CompareTo(a[k]) <= 0) l--; 

     var tmp = a[k]; 
     a[k] = a[l]; 
     a[l] = tmp; 

     var i = k + 1; 
     var j = a.Count - 1; 
     while(i<j) 
     { 
      tmp = a[i]; 
      a[i] = a[j]; 
      a[j] = tmp; 
      i++; 
      j--; 
     } 

     return true; 
    } 

Y el código de demostración/prueba:

 var src = "1234".ToCharArray(); 
     do 
     { 
      Console.WriteLine(src); 
     } 
     while (NextPermutation(src)); 

Answer 7

que se encontró la versión Joey Adams para ser el más fácil de leer, pero no pude puerto directamente a C#, debido a la forma en C# se encarga de la determinación del alcance de las variables for-loop. Por lo tanto, esta es una versión ligeramente modificado de su código:

/// <summary> 
/// Performs an in-place permutation of <paramref name="values"/>, and returns if there 
/// are any more permutations remaining. 
/// </summary> 
private static bool NextPermutation(int[] values) 
{ 
    if (values.Length == 0) 
     throw new ArgumentException("Cannot permutate an empty collection."); 

    //Find all terms at the end that are in reverse order. 
    // Example: 0 3 (5 4 2 1) (i becomes 2) 
    int tail = values.Length - 1; 
    while(tail > 0 && values[tail - 1] >= values[tail]) 
     tail--; 

    if (tail > 0) 
    { 
     //Find the last item from the tail set greater than the last item from the head 
     //set, and swap them. 
     // Example: 0 3* (5 4* 2 1) 
     // Becomes: 0 4* (5 3* 2 1) 
     int index = values.Length - 1; 
     while (index > tail && values[index] <= values[tail - 1]) 
      index--; 

     Swap(ref values[tail - 1], ref values[index]); 
    } 

    //Reverse the tail set's order. 
    int limit = (values.Length - tail)/2; 
    for (int index = 0; index < limit; index++) 
     Swap(ref values[tail + index], ref values[values.Length - 1 - index]); 

    //If the entire list was in reverse order, tail will be zero. 
    return (tail != 0); 
} 

private static void Swap<T>(ref T left, ref T right) 
{ 
    T temp = left; 
    left = right; 
    right = temp; 
} 

Answer 8

¿Qué tal un algoritmo recursivo puede llamar iterativamente? Si realmente necesitaras esas cosas como una lista como esa (claramente deberías incluir eso en lugar de asignar un montón de memoria sin sentido). Simplemente podría calcular la permutación sobre la marcha, por su índice.

Al igual que la permutación es una adición de carry-the-one que revierte la cola (en lugar de volver a 0), indexar el valor de permutación específica es encontrar los dígitos de un número en base n luego n-1 y luego n- 2 ... a través de cada iteración.

public static <T> boolean permutation(List<T> values, int index) { 
    return permutation(values, values.size() - 1, index); 
} 
private static <T> boolean permutation(List<T> values, int n, int index) { 
    if ((index == 0) || (n == 0)) return (index == 0); 
    Collections.swap(values, n, n-(index % n)); 
    return permutation(values,n-1,index/n); 
} 

El booleano devuelve si el valor de su índice estaba fuera de los límites. A saber, que se quedaron sin valores n, pero aún le quedaba el índice restante.

Y no puede obtener todas las permutaciones para más de 12 objetos. 12! < Integer.MAX_VALUE < 13!

- Pero es muy, muy bonito. Y si haces muchas cosas mal podría ser útil.

Answer 9

También encontré el algoritmo QuickPerm al que se hace referencia en otra respuesta. Quería compartir esta respuesta además, porque vi algunos cambios inmediatos que uno puede hacer para escribirlo más corto. Por ejemplo, si el conjunto de índices "p" se inicializa de forma ligeramente diferente, se ahorra tener que devolver la primera permutación antes del ciclo. Además, todos esos "while-loops" y "if" ocuparon mucho más espacio.

void permute(char* s, size_t l) { 
    int* p = new int[l]; 
    for (int i = 0; i < l; i++) p[i] = i; 
    for (size_t i = 0; i < l; printf("%s\n", s)) { 
     std::swap(s[i], s[i % 2 * --p[i]]); 
     for (i = 1; p[i] == 0; i++) p[i] = i; 
    } 
} 

Answer 10

Implementé el algoritmo en Javascript.

var all = ["a", "b", "c"]; 
console.log(permute(all)); 

function permute(a){ 
    var i=1,j, temp = ""; 
    var p = []; 
    var n = a.length; 
    var output = []; 

    output.push(a.slice()); 
    for(var b=0; b <= n; b++){ 
    p[b] = b; 
    } 

    while (i < n){ 
    p[i]--; 
    if(i%2 == 1){ 
     j = p[i]; 
    } 
    else{ 
     j = 0; 
    } 
    temp = a[j]; 
    a[j] = a[i]; 
    a[i] = temp; 

    i=1; 
    while (p[i] === 0){ 
     p[i] = i; 
     i++; 
    } 
    output.push(a.slice()); 
    } 
    return output; 
}