Durch alle Permutationen gehen, ein Austausch nach dem anderen

Question

Wie kann ich anhand einer Liste von n verschiedenen Elementen durch jede einzelne Permutation der Elemente springen, die jeweils nur ein Wertepaar austauschen? (Ich nehme an, es ist möglich, es fühlt sich so an, als sollte es sein.)

Was ich suche ist ein Iterator, der die Indizes des nächsten Paars von zu vertauschenden Elementen ergibt, so dass iteriert n! -1 mal wird es durch das n treten! Permutationen der Liste in einer bestimmten Reihenfolge. Wenn es erneut durchlaufen würde, würde die Liste in ihrer Startreihenfolge wiederhergestellt, was ein Bonus wäre, aber es ist keine Voraussetzung. Wenn alle Paare das erste (bzw. das letzte) Element als eines des Paares enthalten, so dass die Funktion nur einen einzigen Wert zurückgeben muss, wäre das auch ein Bonus.

Beispiel: - Für 3 Elemente können Sie das letzte Element abwechselnd mit dem ersten und zweiten Element vertauschen, 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 wahrscheinlich Lösungen in den meisten Sprachen rätseln.

Answer 1

Ah, sobald ich eine Sequenz für n = 4 berechnet habe (mit der Bedingung "immer den ersten Gegenstand gegen einen anderen tauschen"), konnte ich die Sequenz A123400 in der OEIS finden, die mir sagte, ich brauche "Ehrlichs Swap-Methode ".

Google fand mich a C++ implementation, die ich von this unter der GPL nehme. Ich habe auch Knuths fascicle 2b gefunden, die verschiedene Lösungen genau zu meinem Problem beschreibt.

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

Hier ist ein Perlcode, der Ehrlichs Methode basierend auf Knuths Beschreibung implementiert. Bei Listen mit bis zu 10 Items habe ich jeweils getestet, dass es die komplette Permutationsliste korrekt generiert und dann gestoppt hat.

# 
# 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 für die 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 Wunsch Code Python. (Sorry, es ist wahrscheinlich nicht allzu idiomatische Verbesserungsvorschläge willkommen..)

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

Sehen Sie sich die C++ - Standardbibliotheksfunktion next_permuation (...) an. Das sollte ein guter Ausgangspunkt sein.

Answer 3

Ich bin sicher, dass es für Sie zu spät ist, aber ich fand eine schöne Ergänzung zu dieser Frage: Steinhaus–Johnson–Trotter algorithm und seine Varianten genau das tun, wonach du gefragt hast. Außerdem hat es die zusätzliche Eigenschaft, dass es immer benachbarte Indizes tauscht. Ich habe versucht, eine der Varianten (Even) in Java als Iterator zu implementieren und funktioniert 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 leicht sein würde es zu einer unendlichen Iterator zu ändern, die den Zyklus am Ende neu gestartet wird, oder Iterator, der die getauschten Indizes anstelle der nächsten Permutation zurückgibt.

Here ein weiterer Link sammelt verschiedene Implementierungen.

Answer 4

Sie könnten einen Blick auf https://sourceforge.net/projects/swappermutation/ werfen, die eine Java-Implementierung genau Ihrer Anforderungen ist: ein Iterator, der Swaps generiert. Erstellt vor einiger Zeit ein kürzlich aktualisiert.