Выполнение всех перестановок по одной свопинге за один раз

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 в OEIS, которая сказала мне, что мне нужен «метод обмена Ehrlich's swap ».

Google нашел меня a C++ implementation, который, как я предполагаю, от this находится под лицензией GPL. Я также нашел Knuth's fascicle 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

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

Answer 3

Я уверен, что это слишком поздно для вас, но я нашел хорошее дополнение к этому вопросу: Steinhaus–Johnson–Trotter algorithm и его варианты сделать точно что вы просили. Более того, он обладает дополнительным свойством, что он всегда меняет соседние индексы. Я пытался реализовать один из вариантов (даже х) в 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(); 
    } 
} 

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

Here другая ссылка, собирающая различные реализации.

Answer 4

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