« Project Euler : Problem 23 ~ 過剰数 | トップページ | Project Euler : Problem 25 »

2010年5月10日 (月)

Project Euler : Problem 24 ~ 順列

 問題はこちらをご覧ください。

 

 以前書いたように、Haskell には与えられたリストの順列をすべて返す "permutations" という関数があるのですが、この関数はこの問題でいうところの「辞書順」には結果を返してくれません。
 そのため、この問題を "permutations" で解こうとすると、10! = 3628800 個のリストを求めた後、それをソートしてから 100 万番目の数を探さないといけません。
 実際にやってみたのですが、あまりに遅すぎて結果が出るまで待てませんでした。

 そういった経緯もあって、順列の結果を辞書順に返す "permutation" (非常に紛らわしい名前ですいません) を自作しました。

-- リスト ns から n 個を選ぶ順列 permutation :: [a] -> Int -> [[a]] permutation [] _ = [[]] permutation ns n = perm n (length ns - 1) [(ns, [])] where perm 0 _ xs = [a | (_, a) <- xs] perm c n xs = perm (c - 1) (n - 1) $ concatMap (f n) xs f n (xs, ys) = [(as ++ bs, ys ++ [b]) | i <- [0 .. n], let (as, b : bs) = splitAt i xs] problem024 :: [Int] problem024 = (permutation [0 .. 9] 10) !! (1000000 - 1) main = print problem024
 自作の "permutation" はもともと結構速く、並べ替える必要もないし、遅延評価のおかげで 100 万番目を計算した時点で "problem024" は計算を終了するので、自分のノートパソコンで実際に答えが出るまでに 0.25 秒しかかかりませんでした。

 実はこの問題、もっと簡単に速く解くことができます。
 例えば、 [0, 1, 2, 3] というリストの順列を辞書順に並べて、先頭から順に No.0, No.1, No.2 .. と番号をつけたとします。この時の No.15 を考えます。
 ちなみにここからの説明では、 Haskell のリストに合わせて、インデックスは 0 から数え始めることにして、「インデックス 0」を "i0" と表現します。また、n 個の要素をすべて使った順列の総数は n! = 1 × 2 × ... × (n - 1) × n となります。
 i0 に「0」が入る順列は 3! = 6 、 i0 に「1」が入る順列は同じく 3! = 6 となり、15 ÷ 6 = 2 あまり 3 となるので、 No.15 の i0 は「2」になることが分かります。
 i0 に「2」を使ったので、 i1 に入ることのできる数字は [0, 1, 3] ということになります。これを先ほどと同様に考えていくと 2! = 2 なので、 3 ÷ 2 = 1 あまり 1 となるので、 i1 は 1 になります。
 これを繰り返していくと、最終的に No.15 は [2, 1, 3, 0] となります (No.0 から始まっていることに注意!)。
 これらの考えを関数にまとめたのが、"permutationCount" です。

-- 順列の総数 permutationSize :: Int -> Int permutationSize n = product [2 .. n] -- xs の順列の n 番目の要素を返す。(0 番目から数え始める) permutationCount :: [a] -> Int -> [a] permutationCount xs 0 = xs permutationCount xs n = b : permutationCount (as ++ bs) r where (q, r) = quotRem n $ permutationSize (length xs - 1) (as, b : bs) = splitAt q xs problem24 :: [Int] problem24 = permutationCount [0 .. 9] (1000000 - 1) main = print problem24
 こちらの解き方は、直接 100 万番目を求めるので、約 0.005 秒で答えが出ました。

« Project Euler : Problem 23 ~ 過剰数 | トップページ | Project Euler : Problem 25 »

Haskell」カテゴリの記事

Project Euler」カテゴリの記事

コメント

コメントを書く

コメントは記事投稿者が公開するまで表示されません。

(ウェブ上には掲載しません)

トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/112020/48326591

この記事へのトラックバック一覧です: Project Euler : Problem 24 ~ 順列:

« Project Euler : Problem 23 ~ 過剰数 | トップページ | Project Euler : Problem 25 »

2016年7月
          1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31            
フォト

最近のトラックバック

無料ブログはココログ