Пройти через все перестановки по одному обмену за раз

Question

Учитывая список n различных элементов, как я могу пройти через каждую перестановку элементов, заменяющих только одну пару значений за раз? (Я предполагаю, что это возможно, это, безусловно, кажется, что это должно быть.)

Я ищу итератор, который дает индексы следующей пары элементов, чтобы обмениваться, так что, если итерация n! -1 раза он проходил через N! перестановки списка в некотором порядке. Если бы он снова повлиял на него, восстановит список в своем стартовом порядке, это будет бонусом, но это не требование. Если все пары включают первый (соответствующий последний) элемент как один из пары, так что функция должна вернуть только одно значение, это также будет бонусом.

Пример:-Для 3 элементов вы можете поменяться последним элементом с первым и вторым элементами, чтобы пройти через перестановки, а именно: (ABC) SWAP 0-2 => (CBA) 1-2 (CAB) 0-2 ( BAC) 1-2 (BCA) 0-2 (ACB).

Я буду реализовать в C, но, вероятно, могу избавиться от решений на большинстве языков.

Answer 1

Ах, как только я рассчитал последовательность для n = 4 (с «всегда обмениваться первым элементом с другим« ограничением »), я смог найти последовательность A123400 В OEI, который сказал мне, что мне нужен «Метод обмена Эрлиха».

Google нашел меня реализация C ++, что я предполагаю от это под GPL. Я также нашел Кнут пульса 2b который описывает различные решения именно для моей проблемы.

Как только у меня будет протестированная реализация C, я обновлю это с помощью кода.

Вот какой -то код Perl, который реализует метод Эрлиха на основе описания Кнута. Для списков до 10 пунктов я проверял в каждом случае, что он правильно сгенерировал полный список перестановок, а затем остановился.

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

Пример использования:

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

По запросу, код Python. (Извините, это, вероятно, не слишком идиоматическое. Предложения по улучшению приветствуются.)

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

Я уверен, что для вас уже слишком поздно, но я нашел хорошее дополнение к этому вопросу: Стейнхаус -Джонсон -Алгоритм И его варианты делают именно то, о чем вы просили. Более того, у него есть дополнительное свойство, которое он всегда меняет смежные индексы. Я попытался реализовать один из вариантов (даже) в Java в качестве итератора и хорошо работает:

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

Было бы легко изменить его на бесконечный итератор, который перезагружает цикл в конце, или итератор, который вернет замены индексы вместо следующей перестановки.

Здесь Другая ссылка собирает различные реализации.

Answer 3

Посмотрите на стандартную функцию библиотеки C ++ Next_permuation (...). Это должно быть хорошей отправной точкой.

Answer 4

Вы могли бы взглянуть на https://sourceforge.net/projects/swappermutation/ которая является реализацией Java именно ваших требований: итератор, который генерирует свопы. Создал это некоторое время назад недавно обновленным.