Pasando a través de todas las permutaciones de un intercambio en un momento

Question

Dada una lista de n elementos distintos, ¿cómo puedo pasar por cada permutación de los elementos intercambiando sólo un par de valores en un momento? (Supongo que es posible, sin duda se siente como debería ser).

Lo que estoy buscando es un iterador que arroja los índices del siguiente par de elementos para intercambiar, de modo que si se itera n! -1 veces va a pasar por el n! permutaciones de la lista en algún orden. Si repetirlo una vez más restauraría la lista a su orden de inicio sería una bonificación, pero no es un requisito. Si todos los pares implican el primer (resp. El último) elemento como uno de los dos, de modo que la función sólo tiene que devolver un solo valor, que también sería una ventaja.

Ejemplo: - para 3 elementos, puede intercambiar el último elemento alternativamente con los elementos primero y segundo para recorrer las permutaciones, a saber: (abc) swap 0-2 => (cba) 1-2 (cab) 0-2 (bac) 1-2 (bca) 0-2 (acb).

voy a estar poniendo en práctica en C, pero es probable que pueda descifrar soluciones en la mayoría de los idiomas.

Answer 1

Ah, una vez que calculé una secuencia para n = 4 (con la restricción "siempre cambio el primer elemento con otro"), pude encontrar la secuencia A123400 en el OEIS, que me indicó que necesitaba el "método de intercambio de Ehrlich ".

Google me encontró a C++ implementation, que supongo que de this es bajo la GPL. También encontré Knuth's fascicle 2b que describe diversas soluciones para resolver exactamente mi problema.

Una vez que tengo una aplicación C probado Voy a actualizar esto con código.

Aquí hay un código Perl que implementa el método de Ehrlich basado en la descripción de Knuth. Para listas de hasta 10 elementos, probé en cada caso que generó correctamente la lista completa de permutaciones y luego se detuvo.

# 
# Given a count of items in a list, returns an iterator that yields the index 
# of the item with which the zeroth item should be swapped to generate a new 
# permutation. Returns undef when all permutations have been generated. 
# 
# Assumes all items are distinct; requires a positive integer for the count. 
# 
sub perm_iterator { 
    my $n = shift; 
    my @b = (0 .. $n - 1); 
    my @c = (undef, (0) x $n); 
    my $k; 
    return sub { 
     $k = 1; 
     $c[$k++] = 0 while $c[$k] == $k; 
     return undef if $k == $n; 
     ++$c[$k]; 
     @b[1 .. $k - 1] = reverse @b[1 .. $k - 1]; 
     return $b[$k]; 
    }; 
} 

Ejemplo uso:

#!/usr/bin/perl -w 
use strict; 
my @items = @ARGV; 
my $iterator = perm_iterator(scalar @items); 
print "Starting permutation: @items\n"; 
while (my $swap = $iterator->()) { 
    @items[0, $swap] = @items[$swap, 0]; 
    print "Next permutation: @items\n"; 
} 
print "All permutations traversed.\n"; 
exit 0; 

Por petición, el código de pitón. (Lo siento, es probable que no es demasiado idiomática Propuestas de mejora bienvenida..)

class ehrlich_iter: 
    def __init__(self, n): 
    self.n = n 
    self.b = range(0, n) 
    self.c = [0] * (n + 1) 

    def __iter__(self): 
    return self 

    def next(self): 
    k = 1 
    while self.c[k] == k: 
     self.c[k] = 0 
     k += 1 
    if k == self.n: 
     raise StopIteration 
    self.c[k] += 1 
    self.b[1:k - 1].reverse 
    return self.b[k] 

mylist = [ 1, 2, 3, 4 ] # test it 
print "Starting permutation: ", mylist 
for v in ehrlich_iter(len(mylist)): 
    mylist[0], mylist[v] = mylist[v], mylist[0] 
    print "Next permutation: ", mylist 
print "All permutations traversed." 

Answer 2

Tenga una mirada en el C++ next_permuation función de la biblioteca estándar (...). Ese debería ser un buen punto de partida.

Answer 3

Estoy seguro de que sea demasiado tarde para ti, pero he encontrado una buena adición a esta pregunta: Steinhaus–Johnson–Trotter algorithm y sus variantes hacen exactamente lo que pediste Además, tiene la propiedad adicional de que siempre intercambia índices adyacentes. Traté de poner en práctica una de las variantes (incluso'S) en Java como un iterador y funciona muy bien:

import java.util.*; 

// Based on https://en.wikipedia.org/wiki/Steinhaus%E2%80%93Johnson%E2%80%93Trotter_algorithm#Even.27s_speedup 
public class PermIterator 
    implements Iterator<int[]> 
{ 
    private int[] next = null; 

    private final int n; 
    private int[] perm; 
    private int[] dirs; 

    public PermIterator(int size) { 
     n = size; 
     if (n <= 0) { 
      perm = (dirs = null); 
     } else { 
      perm = new int[n]; 
      dirs = new int[n]; 
      for(int i = 0; i < n; i++) { 
       perm[i] = i; 
       dirs[i] = -1; 
      } 
      dirs[0] = 0; 
     } 

     next = perm; 
    } 

    @Override 
    public int[] next() { 
     int[] r = makeNext(); 
     next = null; 
     return r; 
    } 

    @Override 
    public boolean hasNext() { 
     return (makeNext() != null); 
    } 

    @Override 
    public void remove() { 
     throw new UnsupportedOperationException(); 
    } 

    private int[] makeNext() { 
     if (next != null) 
      return next; 
     if (perm == null) 
      return null; 

     // find the largest element with != 0 direction 
     int i = -1, e = -1; 
     for(int j = 0; j < n; j++) 
      if ((dirs[j] != 0) && (perm[j] > e)) { 
       e = perm[j]; 
       i = j; 
      } 

     if (i == -1) // no such element -> no more premutations 
      return (next = (perm = (dirs = null))); // no more permutations 

     // swap with the element in its direction 
     int k = i + dirs[i]; 
     swap(i, k, dirs); 
     swap(i, k, perm); 
     // if it's at the start/end or the next element in the direction 
     // is greater, reset its direction. 
     if ((k == 0) || (k == n-1) || (perm[k + dirs[k]] > e)) 
      dirs[k] = 0; 

     // set directions to all greater elements 
     for(int j = 0; j < n; j++) 
      if (perm[j] > e) 
       dirs[j] = (j < k) ? +1 : -1; 

     return (next = perm); 
    } 

    protected static void swap(int i, int j, int[] arr) { 
     int v = arr[i]; 
     arr[i] = arr[j]; 
     arr[j] = v; 
    } 


    // ----------------------------------------------------------------- 
    // Testing code: 

    public static void main(String argv[]) { 
     String s = argv[0]; 
     for(Iterator<int[]> it = new PermIterator(s.length()); it.hasNext();) { 
      print(s, it.next()); 
     } 
    } 

    protected static void print(String s, int[] perm) { 
     for(int j = 0; j < perm.length; j++) 
      System.out.print(s.charAt(perm[j])); 
     System.out.println(); 
    } 
} 

Sería fácil modificarlo para un iterador infinito que se reinicia el ciclo al final, o un iterador que devolvería los índices intercambiados en lugar de la siguiente permutación.

Here otro enlace que recopila varias implementaciones.

Answer 4

Puede echar un vistazo a https://sourceforge.net/projects/swappermutation/ que es una implementación de Java exactamente de sus requisitos: un iterador que genera Swaps. Creado esto hace un tiempo una actualización reciente.