Alle Permutationen durch einen Tausch nach dem anderen durchsetzen

Question

Wie kann ich bei einer Liste n unterschiedlicher Elemente jede Permutation der Elemente durchlaufen, die nur ein Wertepaar gleichzeitig tauschen? (Ich nehme an, es ist möglich, es fühlt sich sicherlich so an, als ob es sein sollte.)

Was ich suche, ist ein Iterator, der die Indizes der nächsten Gegenstände zum Austausch liefert, sodass das i-1-fache durch das N! Permutationen der Liste in irgendeiner Reihenfolge. Wenn es erneut iteriert wird, würde die Liste die Liste wiederherstellen, wäre dies ein Bonus, aber es ist keine Voraussetzung. Wenn alle Paare das erste (bzw. das letzte) Element als eines der Paare umfassen, so dass die Funktion nur einen einzelnen Wert zurückgeben muss, wäre dies auch ein Bonus.

Beispiel:-Für 3 Elemente können Sie das letzte Element abwechselnd mit den ersten und zweiten Elementen austauschen, um die Permutationen zu durchlaufen, nämlich: (ABC) Swap 0-2 => (CBA) 1-2 (CAB) 0-2 ( BAC) 1-2 (BCA) 0-2 (ACB).

Ich werde in C implementieren, kann aber in den meisten Sprachen wahrscheinlich Lösungen auskuppeln.

Answer 1

Ah, sobald ich eine Sequenz für n = 4 berechnet habe (mit dem "Immer das erste Element mit einer anderen" Einschränkung), konnte ich eine Sequenz finden A123400 In der Oeis, die mir sagte, ich brauche "Ehrlichs Swap -Methode".

Google hat mich gefunden Eine C ++ - Implementierung, von dem ich annehme Dies ist unter der GPL. Ich habe auch Knuth's gefunden Faszikel 2b Das beschreibt verschiedene Lösungen für genau mein Problem.

Sobald ich eine getestete C -Implementierung habe, werde ich dies mit Code aktualisieren.

Hier ist ein Perl -Code, der die Methode von Ehrlich basierend auf Knuths Beschreibung implementiert. Für Listen bis zu 10 Elemente habe ich jeweils getestet, dass es die vollständige Liste der Permutationen korrekt generiert und anschließend gestoppt wurde.

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

Beispiel Verwendung:

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

Auf Anfrage Python Code. (Entschuldigung, es ist wahrscheinlich nicht übermäßig idiomatisch. Verbesserungsvorschläge begrüßten.)

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

Ich bin sicher, es ist zu spät für Sie, aber ich habe eine schöne Ergänzung zu dieser Frage gefunden: Steinhaus -Johnson -Trotter -Algorithmus Und seine Varianten tun genau das, wonach Sie gefragt haben. Darüber hinaus verfügt es über die zusätzliche Eigenschaft, die es immer benachbarte Indizes austauscht. Ich habe versucht, eine der Varianten (sogar) in Java als Iterator zu implementieren und arbeitet gut:

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

Es wäre einfach, es an einen unendlichen Iterator zu modifizieren, der den Zyklus am Ende neu startet, oder an einen Iterator, der die ausgetauschten Indizes anstelle der nächsten Permutation zurückgeben würde.

Hier Ein weiterer Link, der verschiedene Implementierungen sammelt.

Answer 3

Schauen Sie sich die Funktion c ++ Standardbibliothek an. Next_perMuation (...). Das sollte ein guter Ausgangspunkt sein.

Answer 4

Sie könnten sich ansehen https://sourceforge.net/projects/swappermutation/ Dies ist eine Java -Implementierung von genau Ihre Anforderungen: ein Iterator, der Swaps generiert. Erstellt dies vor einiger Zeit eine kürzlich aktualisierte.