逐步完成所有排列交换 [英] 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计算了一个序列（总是将第一个项目与另一个项目交换约束），我能够在OEIS中找到序列 A123400 。我需要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".

谷歌找到我一个C ++实现，这是什么我假设这个属于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\n";
while (my $swap = $iterator->()) {
    @items[0, $swap] = @items[$swap, 0];
    print "Next permutation: @items\n";
}
print "All permutations traversed.\n";
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屋！