1

0 から 9 までの数字のリストを取得して、リストのすべての順列を返そうとしています。期待される結果をある程度返す 2 つの異なる関数を思いつきましたが、どちらもまさに私が目指しているものではありません。以下は、1 サイクルで正しい結果を返すものです。

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]

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

これで、7 がシフトするまで問題なく動作し、2 番目ごとの数字に移動します。カウントがごちゃごちゃしてると思うんだけど、行ってみたら見えない？

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までのすべての順列を生成することではなく（これは遅すぎます）、100万番目の順列が何であるかを計算することです。あります！n 個のアイテムを配置する方法 - これをシーケンスの末尾で再帰的に使用して、100 万番目の配置に到達するために再配置する必要があるサブシーケンスの数を計算し、そこから配置がどうあるべきかを判断できます。

もっと似たようなものを書く必要があります

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