Продвижение посредством всех перестановок одна подкачка за один раз
Учитывая список n отличных объектов, как я могу ступить посредством каждой перестановки объектов, подкачивающих всего одну пару значений за один раз? (Я предполагаю, что это возможно, конечно, такое чувство, что это должно быть.)
То, что я ищу, является итератором, который приводит к индексам следующей пары объектов для свопинга, такой что, если выполнено с помощью итераций n!-1 раз это ступит через n! перестановки списка в некотором порядке. Если итерация его еще раз восстановила бы список к своему стартовому порядку, который будет премией, но это не требование. Если все пары включают первое (resp. последнее) элемент как одна из пары, так, чтобы функция только возвратила единственное значение, которое также было бы премией.
Пример:-для 3 элементов, можно поочередно подкачивать последний элемент с первыми и вторыми элементами для цикличного выполнения посредством перестановок, то есть: (b c), подкачивают 0-2 => (c b a) 1-2 (c b) 0-2 (b c) 1-2 (b c a) 0-2 (c b).
Я буду реализовывать в C, но могу, вероятно, разрешить решения на большинстве языков.
2 ответа
Ах, однажды я вычислил последовательность для n=4 (с ограничением "всегда поменяйте первый элемент на другой"), Я смог найти последовательность A123400 в OEIS, которая сказала мне, что мне нужен "метод подкачки Эрлиха".
Google нашел мне реализацию C++, которая, как я предполагаю, из этого находится под GPL. Я также нашел пучок Кнута 2b, который описывает различные решения именно моей проблемы.
Как только я проверю реализацию на Си, я обновлю ее кодом.
Вот несколько перловых кодов, которые реализуют метод Эрлиха, основанный на описании Кнута. Для списков до 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;
По запросу, питоновый код. (Извините, наверное, это не слишком идиотизм. Предложения по улучшению приветствуются)
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."
Взгляните на стандартную библиотечную функцию C++ next_permuation(...). Это должно быть хорошей отправной точкой.