Ах, как только я вычислил последовательность для n = 4 (с ограничением «всегда заменять первый элемент другим»), я смог найти последовательность A123400 в OEIS, которая сказала мне нужен "метод обмена Эрлиха".
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."