順列です．生成しちゃいましょう．
事の発端はProjectEulerで，それまでほったらかしてたPandigital系の問題解く際に必要になったので．Google Code Jamでも使ったっぽい．
単純生成
n個の相異なる集合{a_1, a_2, …, a_n}に対して，
- a_1を除いた集合{a_2, a_3, …, a_n}から生成される順列の頭にa_1を
- a_2を除いた集合{a_1, a_3, …, a_n}から生成される順列の頭にa_2を
- …
- a_nを除いた集合{a_1, a_2, …, a_(n-1)}から生成される順列の頭にa_nを
つないで生成．再帰．
# -vim- fileencoding: utf-8
def perm(elements, length, dup=False):
if length < 1 or len(elements) < length and dup == False: return []
elif len(elements) == 1: return [elements]
elif length == 1: return [i for i in elements]
else:
new_perm = []
for i in elements:
buf = elements
if dup == False: buf = elements.replace(i, "")
for j in perm(buf, length - 1, dup):
new_perm.append(i + j)
return new_perm
if __name__ == "__main__":
import time
seed = "abcdefghi"
st = time.time()
val = perm(seed, 9)
et = time.time()
if len(val) < 100:
print("permutation generated {0} sec. {1} items, {2}".format(et - st, len(val), val))
else:
print("permutation generated {0} sec. {1} items".format(et - st, len(val)))- 処理時間
- 要素数9桁・重複無し(dup == False)で平均6.3秒．
- 利点
- 関数に与える集合がsortされてるなら，返ってくる順列もsortされてる．重複の有り無しのスイッチを簡単につけれる
- 難点
- 遅い．その上メモリを喰う．一番軽かった上記のものでおよそ26MB消費．seedと返ってくるものをlistにした場合およそ163MB喰った．
- 備考
- algorithmとして最初に思いついたもので簡単．…だけども，下の使った方が良い．これを使う状況は無いと思われます．
高速生成
集合{a_1, a_2, …, a_(n-1)}から生成される長さk-1の順列それぞれに対して，a_nを両端と文字の間のk箇所に挿入して，集合{a_1, a_2, …, a_n}から生成される長さkの順列を得る．
# -vim- fileencoding: utf-8
def permutation(elements, length, dup=False):
def __core(item, elements):
if elements == []: return [item]
return [i[:j] + item + i[j:] for i in elements for j in range(len(i) + 1)]
new_perm = []
for i in elements: new_perm = __core(i, new_perm)
return new_perm
if __name__ == "__main__":
import time
seed = "".join([str(i) for i in range(1,10)])
st = time.time()
val = permutation(seed, 9)
#val.sort()
et = time.time()
if len(val) < 200:
print("permutation generated {0} sec. {1} elements, {2}".format(et - st, len(val), val))
else:
print("permutation generated {0} sec. {1} elements".format(et - st, len(val)))- 処理時間
- 要素数9桁で平均0.7秒弱．
- 利点
- はやい．
- 難点
- sortされない．
- 備考
- ある集合から生成される順列がすべて必要な場合にこれを使うと良いんじゃないでしょうか．
順次生成
いくつかの過程を経ます．生成された順列p_1,p_2,…,p_nの直後の順列は
- p_1,p_2,…,p_nを右から左に見ていき，最初にp_j < p_(j+1)となる位置jを求める
- 部分列p_(j+1),p_(j+2),…,p_nを左から右に見ていき，最初にp_j > p_kとなる位置k（該当無しの場合k = n + 1）を求める
- p_jとp_(k-1)を交換
- 部分列p_(j+1),…,p_j,p_k,…,p_nを逆順に並び替えてp_n,…,p_k,p_j,…,p_(j+1)にする
で与えられる．
# -vim- fileencoding: utf-8
def next_perm(element):
j = len(element) - 2
while element[j] >= element[j + 1] and j > 0: j -= 1
#while element[j] <= element[j + 1] and j > 0: j -= 1
k = j + 1
while element[j] <= element[k]:
#while element[j] >= element[k]:
k += 1
if k >= len(element): break
np = element[:j] + element[k - 1]
buf = ""
for i in element[j + 1:k - 1] + element[j] + element[k:]:
buf = i + buf
return np + buf
if __name__ == "__main__":
import time
seed = list("123456789")
seed1 = "".join(seed)
seed.reverse()
seed2 = "".join(seed)
st = time.time()
val = [seed1]
while seed2 != seed1:
seed1 = next_perm(seed1)
val.append(seed1)
et = time.time()
if len(val) < 100:
print("permutation generated {0} sec. {1} items, {2}".format(et - st, len(val), val))
else:
print("permutation generated {0} sec. {1} items".format(et - st, len(val)))- 処理時間
- 要素数9桁で平均3.2秒弱．
- 利点
- 辞書順で生成．辞書順で隣接する順列を容易に求めることができる（一つ前の順列を求める場合はnext_permのコメントアウトしてある行をその直上と入れ替えるだけ）
- 難点
- 各要素が順序集合の元である必要が求められるので，たとえば{＋，－，×，÷}の様な集合に対しては使えない（ここら辺，実際の所は言語の仕様に依りますが）．
- 備考
- これといった難点が見つかりません．少なくとも，全順列生成のためのalgorithmでは無い，とだけは言えますが．それでも最初のalgorithmより速いですけど．
おまけ：階乗進数
階乗進数を使って順列を生成する場合，生成された順列を辞書順で並べたときのindex (>= 0)を指定してやれば，直接その番号に対応する順列を生成できます．
# -vim- fileencoding: utf-8
def fact(n):
#if n <= 1: return 1
#return n * fact(n - 1)
return [1,1,2,6,24,120,720,5040,40320,362880][n]
def toFact(val):
#3317 => "4330210"
dig = []
count = 1
while val > count:
dig.append(val % count)
val = val // count
count += 1
dig.append(val)
string = ""
for i in dig:
string = str(i) + string
return string
def nextFact(val):
val = val[:-2] + str(int(val[-2]) + 1) + "0"
next = "0"
for i in range(-2, -1 * len(val), -1):
if int(val[i]) >= -1 * i:
next = "0" + next
val = val[:i - 1] + str(int(val[i - 1]) + 1) + val[i:]
else:
next = val[i] + next
if int(val[0]) == len(val): return "maximum"
else:
next = val[0] + next
return next
def toDec(val):
#"4330210" => 3317
digval = [fact(i) for i in range(len(val) - 1, -1, -1)]
dec = 0
count = 0
for i in val:
dec += int(i) * digval[count]
count += 1
return dec
def map_prm(index, elements):
buf = elements[:]
idxToFact = toFact(index)
if len(buf) > len(idxToFact): idxToFact = idxToFact.zfill(len(buf))
val = ""
for i in idxToFact:
val += buf[int(i)]
buf.pop(int(i))
return val
if __name__ == "__main__":
print("decimal:{0} => factoradic:{1}".format(3317, toFact(3317)))
print("factoradic:{0} => decimal:{1}".format("4330210", toDec("4330210")))
print("(factoradic){0} + 1 => {1}".format("2423110", nextFact("2423110")))
print("\\n-----------------------------------------\\n")
elems = [str(i) for i in range(1, 6)]
n = 71
print("decimal:{0} =>".format(n))
print(" factoradic:{0}".format(toFact(n)))
print(" {0}th permutation generated from {1}:{2}".format(n + 1, elems, map_prm(n, elems)))たとえば，十進数71に対応する階乗進数は"23210"で，{1,2,3,4,5}から生成される順列の辞書順での71番目（indexが0からなので実際には72番目）を求める場合，階乗進数のそれぞれの数を要素の集合のindexに対応づける事になります．具体的には，集合{1,2,3,4,5}に対して以下のような対応付けとなります．
- 階乗進数の左端が"2"なので，{1,2,3,4,5}のindex=2，つまり"3"を“取り出す”，以下同様に
- 階乗進数の左から2番目が"3"なので，{1,2,4,5}のindex=3（"5"）を取り出す
- 左から3番目が"2"なので，{1,2,4}のindex=2（"4"）を取り出す
- 左から4番目が"1"なので，{1,2}のindex=1（"2"）を取り出す
- 左から5番目が"0"なので，{1}のindex=0（"1"）を取り出す
このようにして順に取り出したものをつなぐと35421となり，これが{1,2,3,4,5}から生成される順列を辞書順に並べた場合の(71 + 1)番目に該当する，と．
まとまらないまとめ
最初のalgorithm以外重複には対応してませんし，一つ目のalgorithmも入力として重複集合は許可してません．
入力集合に要素の重複を許可するのであれば，重複してる要素とその数を検出する関数を別個につけたい所です．覚えてればそのうちやるかもしれません．