一次一个交换遍历所有排列 [英] Stepping through all permutations one swap at a time
问题描述
给定一个包含 n 个不同项目的列表,我如何逐步遍历项目的每个排列,一次只交换一对值?(我认为这是可能的,当然感觉应该是.)
Given a list of n distinct items, how can I step through each permutation of the items swapping just one pair of values at a time? (I assume it is possible, it certainly feels like it should be.)
我正在寻找的是一个迭代器,它产生下一对要交换的项目的索引,这样如果迭代 n!-1 次,它将逐步通过 n!以某种顺序排列列表.如果再次迭代它会将列表恢复到其起始顺序,那将是一个奖励,但这不是必需的.如果所有对都将第一个(分别是最后一个)元素作为其中一个元素,那么函数只需要返回一个值,那也将是一个奖励.
What I'm looking for is an iterator that yields the indices of the next pair of items to swap, such that if iterated n!-1 times it will step through the n! permutations of the list in some order. If iterating it once more would restore the list to its starting order that would be a bonus, but it isn't a requirement. If all pairs involve the first (resp. the last) element as one of the pair, so that the function only needs to return a single value, that would also be a bonus.
示例:- 对于 3 个元素,您可以将最后一个元素与第一个和第二个元素交替交换以循环排列,即:(abc) swap 0-2 => (cba) 1-2 (cab) 0-2 (bac) 1-2 (bca) 0-2 (acb).
Example:- for 3 elements, you can swap the last element alternately with the first and second elements to loop through the permutations, viz: (a b c) swap 0-2 => (c b a) 1-2 (c a b) 0-2 (b a c) 1-2 (b c a) 0-2 (a c b).
我将在 C 中实现,但可能会在大多数语言中找到解决方案.
I'll be implementing in C, but can probably puzzle out solutions in most languages.
推荐答案
啊,一旦我计算了一个 n=4 的序列(使用总是将第一项与另一个交换"约束),我就能找到序列A123400 在 OEIS 中,它告诉我需要Ehrlich 的交换方法".
Ah, once I calculated a sequence for n=4 (with the "always swap the first item with another" constraint), I was able to find sequence A123400 in the OEIS, which told me I need "Ehrlich's swap method".
Google 找到了我 一个 C++ 实现,我假设 this 属于 GPL.我还发现了 Knuth 的 分册 2b,它描述了各种解决我的问题.
Google found me a C++ implementation, which I assume from this is under the GPL. I've also found Knuth's fascicle 2b which describes various solutions to exactly my problem.
一旦我有一个经过测试的 C 实现,我会用代码更新它.
这是一些基于 Knuth 描述实现 Ehrlich 方法的 perl 代码.对于最多 10 个项目的列表,我在每种情况下都测试了它是否正确生成了完整的排列列表,然后停止了.
Here's some perl code that implements Ehrlich's method based on Knuth's description. For lists up to 10 items, I tested in each case that it correctly generated the complete list of permutations and then stopped.
#
# 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
";
while (my $swap = $iterator->()) {
@items[0, $swap] = @items[$swap, 0];
print "Next permutation: @items
";
}
print "All permutations traversed.
";
exit 0;
根据要求,python 代码.(抱歉,这可能不太习惯用语.欢迎提出改进建议.)
By request, python code. (Sorry, it probably isn't overly idiomatic. Suggestions for improvement welcomed.)
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."
这篇关于一次一个交换遍历所有排列的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!