Facendo un passo attraverso tutte le permutazioni uno scambio alla volta

Question

Dato un elenco di n elementi distinti, come posso scorrere ogni permutazione degli elementi scambiano solo un paio di valori in un momento? (Suppongo che sia possibile, certamente si sente come dovrebbe essere.)

Quello che sto cercando è un iteratore che produce gli indici della prossima coppia di elementi da scambiare, in modo tale che se iterata n! -1 volte farà un passo attraverso il n! permutazioni della lista in un certo ordine. Se l'iterazione ancora una volta sarebbe ripristinare l'elenco al suo ordine di partenza che sarebbe un bonus, ma non è un requisito. Se tutte le coppie comportano il primo (risp. L'ultimo) elemento come uno della coppia, in modo che la funzione ha solo bisogno di restituire un singolo valore, che sarebbe anche un vantaggio.

Esempio: - 3 elementi, è possibile scambiare l'ultimo elemento alternativamente con il primo e secondo elemento a cappio attraverso le permutazioni, cioè: (abc) scambiare 0-2 => (cba) 1-2 (cabina) 0 -2 (bAC) 1-2 (BCA) 0-2 (ACB).

Sarò di applicazione in C, ma probabilmente può decifrare soluzioni nella maggior parte delle lingue.

Answer 1

Ah, una volta che ho calcolato una sequenza per n = 4 (con la "scambiare sempre il primo elemento con un altro" vincolo), sono stato in grado di trovare la sequenza A123400 nel OEIS, che mi ha detto che ho bisogno "metodo di scambio di Ehrlich".

Google mi ha trovato un C ++ implementazione , che presumo da questo è sotto la licenza GPL. Ho anche trovato fascicolo 2b di Knuth che descrive vari soluzioni a esattamente il mio problema.

Una volta che ho un'implementazione C testato aggiornerò questo con il codice.

Ecco un po 'di codice Perl che implementa il metodo di Ehrlich basato sulla descrizione di Knuth. Per le liste fino a 10 elementi, ho provato in ogni caso che correttamente ha generato l'elenco completo delle permutazioni e poi si fermò.

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

uso Esempio:

#!/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;

A richiesta, il codice Python. (Ci dispiace ma probabilmente non è eccessivamente idiomatica. Proposte di miglioramento accolto.)

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

Sono sicuro che sia troppo tardi per voi, ma ho trovato una bella aggiunta a questa domanda: Steinhaus-Johnson-Trotter e le sue varianti fanno esattamente quello che hai chiesto. Inoltre ha la proprietà aggiuntiva che scambia sempre indici adiacenti. Ho cercato di implementare una delle varianti (anche per) in Java come un iteratore e funziona bene:

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

Sarebbe facile da modificare a un iteratore infinita che riprende il ciclo alla fine, o un iteratore che restituirebbe gli indici scambiati invece della permutazione successiva.

qui altro link raccogliendo varie implementazioni.

Answer 3

Dai un'occhiata al C ++ next_permuation funzione della libreria standard (...). Questo dovrebbe essere un buon punto di partenza.

Answer 4

Si potrebbe avere uno sguardo a https://sourceforge.net/projects/swappermutation/ che è un'implementazione Java di esattamente si requisiti: un iteratore che genera Swap. Creato questo qualche tempo fa un recentemente aggiornato.