お久しぶりです。

今回は与えられた要素から考えうる順列を全て洗い出すスクリプトを書いてみようと思います。

できそうでできずにインターンで苦しんだのでゆっくり考えてみたのでメモがわりに。

順列とは

異なる数個のものを順序づけて一列に並べる並べ方の一つ一つをいう。n個からr個とる順列（n個のものからr個選んで得られる順列）の数を(/n)P(/r)と書く。

引用: kotobank.jp

だそうです。

例えば

list = ['a','b','c']

から３つ取り出して並べる方法は 3! 通り。

全て書きだすとこんな感じ。

['a', 'b', 'c'] ['a', 'c', 'b'] ['b', 'a', 'c'] ['b', 'c', 'a'] ['c', 'a', 'b'] ['c', 'b', 'a']

なんてことない、中学生レベルのお話ですね。

コード

              #!/usr/bin/python
              
              # ans : 組み合わせの数 order : 並び順
              ans = 0
              order = []
              
              def make_segment(array, order, n):
                  if n == len(array):
                      print order
                      global ans
                      ans += 1
                      return
                  for i in range(len(array)):
                      if array[i] not in order:
                          order.append(array[i])
                          make_segment(array, order, n+1)
                          order.pop()
                      else:
                          continue
              # main
              array = ['0','1','2','3','4','5','6','7','8','9']
              
              make_segment(array, order, 0)
              print ans
              

テスト用に0~9の文字列を作ってやってます。

アルゴリズムとしては単純なもので、

• どんどん下に掘っていってorderに要素を積んでいく
• orderに既にあるものは積まずにcontinue
• orderが渡された配列の長さと一致した時点でprint,return

という感じです。

ただ、問題点として要素数が9以上になると処理時間が増えるところですね。。。

もうちょっといろいろ勉強しよう。

ちゃんちゃん。

---

※この記事は WordPress に投稿した記事を変換したものです。一部不自然な表示があるかも知れません。ご了承ください。また、記事タイトル先頭の * は WordPress から移行した記事である印です。