ハスケル：大きなコンビナトリアルリストを扱うには？

Question

ちょうど最近、私は基本的にオンラインゲームからシンプルなシステムをシミュレートするプログラムを書こうとしました。その背後にあるアイデアは、セットから最も可能性の高い統計効率のために、最も効率的なアイテムのセットをプログラムに計算させることです。これをもう少し明確にするために： あなたは8つのアイテムスロットと74の異なるアイテムを持っています。どのアイテムも2回使用することはできません。また、どのアイテムがどのスロットにあるかは関係ありません。私はまだ1つの統計情報を計算しようとしていません、私は先に立ち往生しています！

したがって、この問題は、フィルタリングする前に（74^8）、フィルタした後に（74を8つ選択する）可能性の数です。 私が頭を試してみると、私のプログラムは遅れて始まります（permu '2）。 私はHaskellが無限リストを扱うことになっていることを知っているので、899兆件のリストのリストとはどのように動作しますか？よくわかっていますが、それはPCに多大な容量を必要とすることは明らかですが、私はここで質問しています。

ハスケルで大きなリストを扱うにはどうすればいいですか？このような

機能簡素化ルックス：

quicksort :: (Ord a) => [a] -> [a] 
quicksort [] = [] 
quicksort [a] = [a] 
quicksort (x:xs) = (quicksort [y | y <- xs, y <= x]) ++ [x] ++ (quicksort [z | z <- xs , z > x]) 

eliminatedouble [] = [] 
eliminatedouble (x:xs) = if x `elem` xs then eliminatedouble xs else x:(eliminatedouble xs) 

permu' n | n>8 = error "8 is max" 
     | otherwise = eliminatedouble (filter allSatisfied (generate n)) 
    where 
     generate 0 = [[]] 
     generate x = [quicksort (a:xs) | a <- [1..74], xs <- generate (x-1)] 
     allSatisfied [] = True 
     allSatisfied (x:xs) = (checkConstraint x xs) && (allSatisfied xs) 
     checkConstraint x xs = not (doubled x xs) 
     doubled x xs = x `elem` xs 

はすべて、このように安価を行う方法を知って興味深いものになるだろう。

ありがとうございます。

Answer 1

これは、必要以上に難しくしています。私の通訳で

choose 0 xs = [[]] 
choose n [] = [] 
choose n (x:xs) = map (x:) (choose (n-1) xs) ++ choose n xs 

、choose 5 [1..74]は、すべてのエントリを計算するのに約22秒かかり、choose 6 [1..74]は273秒かかります。さらに、choose 8 [1..74]はすぐに組み合わせて魅了され始めます。私はそれらをすべて生成するのに約6時間かかると推測しています。 N.B.これは通訳者の中にあり、最適化や他の素朴さは進行していません。あなたがGHCにどのようにして機会を与える機会を与えれば、もっと速く進む可能性があります。

choose 8 [1..74]のそれぞれの要素に対して何か重要な計算を行うつもりであると仮定すると、時間の大部分をスケジューリングするか、徹底的な検索を行わないソリューションについて考えることをお勧めします。おおよその答え、または検索スペースの大規模な、興味深いスワスを切り取るためにいくつかの枝刈りを行う方法を考え出す。