プロジェクトオイラー Problem24

「プロジェクト　オイラー」の問題をpythonでやってみます。

出典：Project Euler（日本語翻訳サイト）
参考：サイエンスもの置き場　プロジェクトオイラーを遊び倒すガイド（初級編）

Problem 24
順列とはモノの順番付きの並びのことである.
たとえば, 3124は数1, 2, 3, 4の一つの順列である.
すべての順列を数の大小でまたは辞書式に並べたものを辞書順と呼ぶ.
0と1と2の順列を辞書順に並べると
012 021 102 120 201 210
になる.
0,1,2,3,4,5,6,7,8,9からなる順列を辞書式に並べたときの100万番目を答えよ.


私の解答例は以下です。
－－－－－

def g(n):
	if n<=1: return 1
	else: return n*g(n-1)
	
def f(s, n):
	L0, L1 = sorted([i for i in s]), []
	if n<1 or g(len(s))<n: return False
	for i in xrange(len(s), 0, -1):
		u = g(i)/i
		v = (n-1)/u
		n -= u*v
		L1.append(L0[v])
		L0.pop(v)
	return "".join(L1)
	
print f("0123456789", 1000000)

－－－－－
主要部分の考え方は以下の通りです。
手始めに、例として、リストL=[0,1,2]という3個の要素がある場合を考えます。
辞書順パターン全体は3!=6通りです。
各パターン最初の要素には、3!パターンを3で割った数ずつ、元のリストの要素が使われます。
(3!/3)*0番目～(3!/3)*1番目までは、最初の要素は元の1番目の要素「0」
(3!/3)*1番目～(3!/3)*2番目までは、最初の要素は元の2番目の要素「1」
(3!/3)*2番目～(3!/3)*3番目までは、最初の要素は元の3番目の要素「2」

これをリストLに要素がm個ある場合に拡張すると以下の通りです。
辞書順パターン全体はm!通りです。
各パターン最初の要素には、m!パターンをmで割った数ずつ、元のリストの要素が使われます。
(m!/m)*0番目～(m!/m)*1番目までは、最初の要素は元の1番目の要素
(m!/m)*1番目～(m!/m)*2番目までは、最初の要素は元の2番目の要素
・・・
(m!/m)*(m-1)番目～(m!/m)*m番目までは、最初の要素は元のn番目の要素
上記の考え方をpythonで実装しました。

２つの関数を使用しています。
１．g(n)
・階乗。problem 20から流用しました。
・終了条件を改良して、nが1未満の値でもエラーにならないようにしました。

２．f(s, n)
・文字列sの文字1つひとつを辞書順に並べたときのn番目のパターンを返却します。
・L0, L1 = sorted([i for i in s]), []
　L0は文字1つひとつを要素にしてソートしたリストです。
　L1はn番目の辞書順n番目の状態のリストです。初期状態は空リストです。
・if n<1 or g(len(s))<n: return False
　n番目ということなのでn<1なら処理しません。
　nは要素n個の辞書順パターン数（nの階乗=n!）を超えることはなく、この場合も処理しません。
・for i in xrange(len(s), 0, -1):
　ループ変数iは未使用の要素数です。引数sの文字数から0まで1ずつ減らしていきます。
・u = g(i)/i
　各未使用要素が最上位にくる、パターン数の幅です。（iの階乗値）÷iです。
・v = (n-1)/u
　未使用要素のうち、n番目のパターンにあたる値の、元リストでのindex番号です。
　何番目かの値nを、最上位値が同一であるパターン数の幅uで割ります。
・n -= u*v
　何番目かの値nのうち、要素未定でまだ定まっていない残り分、あといくつ進めばいいかを示します。
・L1.append(L0[v])
　元リストのindex番号vの要素を求めるリストの最後に追加します。
・L0.pop(v)
　求めるリストに追加したので、元リストからindex番号vの要素を削除し、次のループにいきます。
・return "".join(L1)
　ループ終了後、並び終えたリストL1を連結して、文字列に変換して戻り値とします。
　
３．関数の外
・上記の関数fに、文字列"0123456789"と、1000000（番目）を渡せば求める値になります。


解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
2783915460

（追記）
・20120715
　ソースコード部分にSyntaxHighlighterを導入。