Ах, как только я вычислил последовательность для n=4 (с всегда заменой первого элемента другим ограничением), я смог найти последовательность A123400 в OEIS, где мне сказали, что мне нужен метод подкачки Эрлиха.
Google нашел мне реализацию C++, которую я предполагаю from это находится под лицензией 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."
person
Hugo van der Sanden
schedule
05.01.2010