Parcourant toutes les permutations d'un échange à la fois

Question

Étant donné une liste de n éléments distincts, comment puis-je parcourir chaque permutation des éléments swapping juste une paire de valeurs à la fois? (Je suppose qu'il est possible, il se sent certainement comme il devrait être.)

Ce que je suis à la recherche est un itérateur qui donne les indices de la paire suivante d'éléments à échanger, de sorte que si n itéré! -1 fois il fait défiler les n! permutations de la liste dans un ordre. Si itérer une fois de plus rétablirait la liste à son ordre de départ qui serait un bonus, mais ce n'est pas une exigence. Si toutes les paires impliquent la première (resp. Le dernier) comme élément de la paire, de sorte que la fonction ne doit renvoyer une valeur unique, ce serait aussi un bonus.

Exemple: - 3 éléments, on peut échanger le dernier élément en alternance avec les premier et second éléments de boucle à travers les permutations, à savoir: (abc) échange 0-2 => (cba) 1-2 (cab) 0 -2 (bac) 1-2 (bca) 0-2 (PBR).

Je vais implantera en C, mais peut sans doute trouver des solutions de puzzle dans la plupart des langues.

Answer 1

Ah, une fois que je calcule une séquence pour n = 4 (avec le « échange toujours le premier élément avec une autre » contrainte), j'ai pu trouver la séquence A123400 dans le OEIS, qui m'a dit que je besoin "méthode d'échange de Ehrlich".

Google m'a trouvé une implémentation C ++ , que je suppose de cette est sous la licence GPL. J'ai aussi trouvé 2b fascicle Knuth qui décrit divers des solutions à mon problème exactement.

Une fois que j'ai une implémentation C testé Je vais mettre à jour ce avec le code.

Voici un code Perl qui implémente la méthode d'Ehrlich basée sur la description de Knuth. Pour les listes jusqu'à 10 articles, je l'ai testé dans chaque cas où il a généré correctement la liste complète des permutations, puis arrêté.

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

Exemple d'utilisation:

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

Sur demande, le code python. (Désolé, il est probablement pas trop idiomatiques. Les suggestions d'amélioration bienvenue.)

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

Je suis sûr qu'il est trop tard pour vous, mais j'ai trouvé un ajout à cette question: algorithme Steinhaus-Johnson-Trotter et ses variantes font exactement ce que vous avez demandé. En outre, il a la propriété supplémentaire que swaps toujours indices adjacents. J'ai essayé de mettre en œuvre l'une des variantes (Even) en Java comme un itérateur et fonctionne 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();
    }
}

Il serait facile de le modifier à un iterator infini qui redémarre le cycle à la fin, ou un itérateur qui renverrait les indices échangés au lieu de la permutation suivante.

Voici un autre lien de collecte différentes implémentations.

Answer 3

Jetez un oeil à la fonction de la bibliothèque standard C de next_permuation (...). Cela devrait être un bon point de départ.

Answer 4

Vous pouvez consulter https://sourceforge.net/projects/swappermutation/ qui est une implémentation Java de vous exactement exigences: un itérateur qui génère Swaps. Créé il y a quelque temps un récemment mis à jour.