Pythonで順列作成
会社の若手でやっている勉強会でこんな問題をみんなで解いてみた。
問題文
5, 4, 3, 2, 1, 0の６つの整数の間（順番は不変）に
「+, -, *, /, =」の演算子を必ず一回ずつ使い（順番は任意）式が成立するような組み合わせを求めよ
開始１０分くらいで、演算子の並びの順列を求めるという問題になり考え始める。
itertoolsを使う
itertoolsというモジュールにpermutationsという関数がある。
from itertools import permutations
[x for x in permutation([1, 2, 3])]
itertoolsに含まれる関数については以下の記事が詳しくていい。
itertoolsモジュールをひと通り眺めてみた - kk6のメモ帳
イテレーション処理に便利な関数が多数含まれている。
自作する
アルゴリズムとして作成するにはどうするのか考える。簡単な例から何かしらの法則性を見つけることにする。
---------------
[1, 2]
-> [1, 2]
-> [2, 1]
2! = 2通り
---------------
[1, 2, 3]
-> [1, 2, 3]
-> [3, 2]
-> [2, 1, 3]
-> [3, 1]
-> [3, 2, 1]
-> [1, 2]
3! = 6通り
---------------
[1, 2, 3, 4]
-> [1 ,2, 3, 4]
-> [4, 3]
-> [3, 2, 4]
-> [4, 2]
-> [4, 3, 2]
-> [2, 3]
-> [2, 1, 3, 4]
-> ...
4! = 24通り
頭から取り出していって、残り２つになったらくるっとする。
残り２つになったらくるっとするというより、くるっとし続けて出来なくなったら空っぽにして頭をひっくり返す。
def permutation(li):
if li == []:
return [[]]
else:
return [[h]+t for i,h in enumerate(li) for t in permutation(li[:i]+li[i+1:])]
残り２つを意識して作ると、なんか複雑になっていく。
ちょっと視点を変えるのがこんなに大変だとは。。。結構時間かかった。
模範解答
この記事にある問題。模範解答もある。
順列生成アルゴリズム - drecom_kiroynのブログ
int n, m[M], i, j;
for(i=0;i<M;i++) m[i]=i;
for(i=M;i>=1;i++) {
n=N % i;
printf("%d", m[n]);
for(j=n;j<i-1;j++) m[j]=m[j+1]; //こんなに短いのに辞書順
N=(int)(N/i);
}
printf("\n");
剰余とか使ってる。なんかかっこいい。
しかし、何かよくわからない。。。
