Pasando a través de todas las permutaciones de un intercambio a la vez

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

Lo que estoy buscando es un iterador que se obtienen los índices de la siguiente par de puntos para intercambiarlos, tal que si iterado n! -1 veces que se paso a través de la n! permutaciones de la lista en algún orden. Si la iteración una vez más restauraría la lista a su orden de salida que sería una ventaja, 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: - por 3 elementos, puede intercambiar el último elemento alternativamente con los primer y segundo elementos a bucle a través de las permutaciones, a saber: (abc) intercambiar 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 idiomas.

Answer 1

Ah, una vez que calcula una secuencia para n = 4 (con la "siempre intercambiar el primer elemento con otro" restricción), yo era capaz de encontrar secuencia A123400 en el OEIS, que me dijo que necesito "método de intercambio de Ehrlich".

Google me encontró una implementación en C ++ , que yo supongo que a partir rel="nofollow este está bajo la GPL. También he encontrado fascículo 2b de Knuth que describe varios soluciones a exactamente mi problema.

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

Aquí hay un código Perl que implementa el método de Ehrlich basado en la descripción de Knuth. Para las listas de hasta 10 elementos, he probado en cada caso que se genera 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 Python. (Lo siento, es probable que no es excesivamente 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

Estoy seguro de que sea demasiado tarde para ti, pero he encontrado una buena adición a esta pregunta: Steinhaus-Johnson-Trotter y sus variantes hacen exactamente lo que usted pidió. Por otra parte 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.

aquí otro enlace recogiendo varias implementaciones.

Answer 3

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

Answer 4

Se puede echar un vistazo a https://sourceforge.net/projects/swappermutation/ cuales es una implementación de Java de exactamente que requisitos: un iterador que genera permutas. Creado este hace algún tiempo un actualizado recientemente.