1

我正在尝试获取包含 0-9 的数字列表并返回列表的所有排列。我想出了两个不同的函数，它们在一定程度上返回了预期的结果，但这都不是我的目标。这是一个返回一个周期的正确结果的方法：

x = [0,1,2,3,4,5,6,7,8,9]

def test(x):
  place_holder = 9
  count = 9
  print x
  while count > 1:
    old_x = x[count]
    x[count] = x[count-1]
    x[count-1] = old_x
    count -= 1
    print x
    if count == 1:
      x.sort()
      place_holder -= 1
      count = place_holder

回报：

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 9, 8]
[0, 1, 2, 3, 4, 5, 6, 9, 7, 8]
[0, 1, 2, 3, 4, 5, 9, 6, 7, 8]
[0, 1, 2, 3, 4, 9, 5, 6, 7, 8]
[0, 1, 2, 3, 9, 4, 5, 6, 7, 8]
[0, 1, 2, 9, 3, 4, 5, 6, 7, 8]
[0, 1, 9, 2, 3, 4, 5, 6, 7, 8]
[0, 9, 1, 2, 3, 4, 5, 6, 7, 8]
[0, 1, 2, 3, 4, 5, 6, 8, 7, 9]
[0, 1, 2, 3, 4, 5, 8, 6, 7, 9]
[0, 1, 2, 3, 4, 8, 5, 6, 7, 9]
[0, 1, 2, 3, 8, 4, 5, 6, 7, 9]
[0, 1, 2, 8, 3, 4, 5, 6, 7, 9]
[0, 1, 8, 2, 3, 4, 5, 6, 7, 9]
[0, 8, 1, 2, 3, 4, 5, 6, 7, 9]
[0, 1, 2, 3, 4, 5, 7, 6, 8, 9]
[0, 1, 2, 3, 4, 7, 5, 6, 8, 9]
[0, 1, 2, 3, 7, 4, 5, 6, 8, 9]
[0, 1, 2, 7, 3, 4, 5, 6, 8, 9]
[0, 1, 7, 2, 3, 4, 5, 6, 8, 9]
[0, 7, 1, 2, 3, 4, 5, 6, 8, 9]
[0, 1, 2, 3, 4, 6, 5, 7, 8, 9]
[0, 1, 2, 3, 6, 4, 5, 7, 8, 9]
[0, 1, 2, 6, 3, 4, 5, 7, 8, 9]
[0, 1, 6, 2, 3, 4, 5, 7, 8, 9]
[0, 6, 1, 2, 3, 4, 5, 7, 8, 9]
[0, 1, 2, 3, 5, 4, 6, 7, 8, 9]
[0, 1, 2, 5, 3, 4, 6, 7, 8, 9]
[0, 1, 5, 2, 3, 4, 6, 7, 8, 9]
[0, 5, 1, 2, 3, 4, 6, 7, 8, 9]
[0, 1, 2, 4, 3, 5, 6, 7, 8, 9]
[0, 1, 4, 2, 3, 5, 6, 7, 8, 9]
[0, 4, 1, 2, 3, 5, 6, 7, 8, 9]
[0, 1, 3, 2, 4, 5, 6, 7, 8, 9]
[0, 3, 1, 2, 4, 5, 6, 7, 8, 9]
[0, 2, 1, 3, 4, 5, 6, 7, 8, 9]

虽然当我在排列中使用另一个列表时，它会产生意想不到的结果：

x = [1,0,2,3,4,5,6,7,8,9]

[1, 0, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 0, 2, 3, 4, 5, 6, 7, 9, 8]
[1, 0, 2, 3, 4, 5, 6, 9, 7, 8]
[1, 0, 2, 3, 4, 5, 9, 6, 7, 8]
[1, 0, 2, 3, 4, 9, 5, 6, 7, 8]
[1, 0, 2, 3, 9, 4, 5, 6, 7, 8]
[1, 0, 2, 9, 3, 4, 5, 6, 7, 8]
[1, 0, 9, 2, 3, 4, 5, 6, 7, 8]
[1, 9, 0, 2, 3, 4, 5, 6, 7, 8]
[0, 1, 2, 3, 4, 5, 6, 8, 7, 9]
[0, 1, 2, 3, 4, 5, 8, 6, 7, 9]
[0, 1, 2, 3, 4, 8, 5, 6, 7, 9]
[0, 1, 2, 3, 8, 4, 5, 6, 7, 9]
[0, 1, 2, 8, 3, 4, 5, 6, 7, 9]
[0, 1, 8, 2, 3, 4, 5, 6, 7, 9]
[0, 8, 1, 2, 3, 4, 5, 6, 7, 9]
[0, 1, 2, 3, 4, 5, 7, 6, 8, 9]
[0, 1, 2, 3, 4, 7, 5, 6, 8, 9]
[0, 1, 2, 3, 7, 4, 5, 6, 8, 9]
[0, 1, 2, 7, 3, 4, 5, 6, 8, 9]
[0, 1, 7, 2, 3, 4, 5, 6, 8, 9]
[0, 7, 1, 2, 3, 4, 5, 6, 8, 9]
[0, 1, 2, 3, 4, 6, 5, 7, 8, 9]
[0, 1, 2, 3, 6, 4, 5, 7, 8, 9]
[0, 1, 2, 6, 3, 4, 5, 7, 8, 9]
[0, 1, 6, 2, 3, 4, 5, 7, 8, 9]
[0, 6, 1, 2, 3, 4, 5, 7, 8, 9]
[0, 1, 2, 3, 5, 4, 6, 7, 8, 9]
[0, 1, 2, 5, 3, 4, 6, 7, 8, 9]
[0, 1, 5, 2, 3, 4, 6, 7, 8, 9]
[0, 5, 1, 2, 3, 4, 6, 7, 8, 9]
[0, 1, 2, 4, 3, 5, 6, 7, 8, 9]
[0, 1, 4, 2, 3, 5, 6, 7, 8, 9]
[0, 4, 1, 2, 3, 5, 6, 7, 8, 9]
[0, 1, 3, 2, 4, 5, 6, 7, 8, 9]
[0, 3, 1, 2, 4, 5, 6, 7, 8, 9]
[0, 2, 1, 3, 4, 5, 6, 7, 8, 9]

它正确地通过九个周期然后回到0-9。所以我可以看到这是因为 x.sort() 调用。所以我把这个函数改成这样：

def exp_test(x):
  static = []
  for i in x:
    static.append(i)
  place_holder = 9
  count = 9
  print x
  while count > 1:
    old_x = x[count]
    x[count] = x[count-1]
    x[count-1] = old_x
    count -= 1
    print x
    if count == 1:
      x = static
      place_holder -= 1
      count = place_holder

现在这工作正常，直到七的转变，它去到每隔一个数字。我想计数搞混了，但是，我通过并没有看到它？

4

2 回答 2

3

尝试x = static在最后一条if语句中修改为x = static[:]. 问题是您只是将名称重新绑定到绑定x到的同一个列表static。您真的想复制static绑定的内容。

于 2012-06-04T02:25:16.967 回答
2

最好的解决方案是

from itertools import permutations

但如果你必须自己写，通常的解决方案是递归的：

def permutations(seq):
    _len = len(seq)
    if _len:
        if _len==1:
            yield seq
        else:
            for p in permutations(seq[1:]):
                for i in range(_len):
                    yield p[:i] + seq[0:1] + p[i:]

编辑：嗯，欧拉问题需要完全不同的方法......诀窍不是生成所有排列到 1,000,000（这太慢），而是计算第百万个排列必须是什么。有n！排列 n 项的方法 - 您可以在序列的尾部递归地使用它来计算必须重新排列多少子序列才能达到第 100 万个排列，并从中计算出必须是什么排列。

你需要写一些更像

def nth_arrangement(seq, n):
    # you have to figure this bit out!
于 2012-06-04T02:22:11.820 回答