0

私は haskell で櫛関数を書いています。必要なことは、カードのデッキを提供するときに、サイズ x のそのデッキから可能な手のすべての組み合わせを提供することです。

これは関連するコードです

combs :: Int -> [a] -> [[a]]
combs 0 _      = [[ ]]
combs i (x:xs) =  (filter (isLength i) y)
            where y = subs (x:xs)
combs _ _      = [ ]

isLength :: Int -> [a] -> Bool
isLength i x
        | length x == i = True
        | otherwise     = False

subs :: [a] -> [[a]]
subs [ ] = [[ ]]
subs (x : xs) = map (x:) ys ++ ys
            where ys = subs xs

しかし、コーム 5 [1..52] を計算するように依頼すると、たとえば、完全なデッキから 5 の手札が得られず、結果が得られず、非常に長い間実行され続け
ます。このアルゴリズムを高速化する方法は?

4

2 に答える 2

3

iアイテムを抽出するx:xsには、次の 2 つの方法があります。

  • を保持し、から要素xのみを抽出しますi-1xs
  • を破棄し、からすべての要素xを抽出しますixs

したがって、解決策は次のとおりです。

comb :: Int -> [a] -> [[a]]
comb 0 _      = [[]]  -- only the empty list has 0 elements
comb _ []     = []    -- can not extract > 0 elements from []
comb i (x:xs) = [ x:ys | ys <- comb (i-1) xs ]  -- keep x case
                ++ comb i xs                    -- discard x case

ところで、上記のコードは、二項係数のよく知られた再帰式を「証明」します。微積分のクラスに参加したことがある場合は、この式を既に満たしている可能性があります。みましょB(k,n) = length (comb k [1..n])う、私たちは持っています

B(k+1,n+1) == B(k,n) + B(k+1,n)

これは、上記のコードの最後の行の直接的な結果です。

于 2014-10-12T17:50:46.763 に答える
3

今、あなたが何をしようとしているのかを理解するのは少し難しいですが、あなたが抱えている問題は、フィルタリングとマッピングを何度も行うことだと思います.

必要なものを取得する簡単な方法は次のとおりだと思います。

module Combinations where

import Data.List (delete)

combs :: Eq a => Int -> [a] -> [[a]]
combs 0 _ = [[]]
combs i xs = [ y:ys | y <- xs, ys <- combs (i-1) (delete y xs) ]

から使用deleteするData.List

組み合わせをすばやく見つけるのに十分なほど怠惰なはずです-もちろん、すべてに時間がかかります;）

λ> take 5 $ combs 5 [1..52]
[[1,2,3,4,5],[1,2,3,4,6],[1,2,3,4,7],[1,2,3,4,8],[1,2,3,4,9]]

どのように機能しますか

yこれは、すべてのカードから最初のカードを選択することによって機能する再帰的組み合わせアルゴリズムの 1 つであり、リストモナド内でxs再帰的に get s the rest of the handys y:ys` をfrom the deck without the selected card削除します (ここではリスト内包表記を使用しています)。and then putting it back together

ところで: そのようなデッキは 311,875,200 あります ;)

リスト内包表記なしのバージョン

システムに問題がある場合に備えて、理解のないバージョンを次に示します。

combs :: Eq a => Int -> [a] -> [[a]]
combs 0 _ = [[]]
combs i xs = do
  y <- xs
  ys <- combs (i-1) (delete y xs)
  return $ y:ys

順列を削除するバージョン

これは、アイテムを昇順でソートOrdするために使用し、その際に順列に関して重複を削除します-これが機能するためには、事前にソートされることが期待されます!xs

注意: chi のバージョンはより少ない制約で動作しており、より優れたパフォーマンスを発揮する可能性もありますが、これは素晴らしく読みやすく、以前のバージョンとうまくいくと思うので、興味があるかもしれません。

Haskell/FP では、最も一般的で抽象的なケースをめぐって争うことはよくあることではありませんが、私はほとんどの人が読みやすさと理解 (コンパイラーのためだけでなくプログラマーのためのコーディング) を目指して努力する環境を形成しています。 ;)

combs' :: Ord a => Int -> [a] -> [[a]]
combs' 0 _  = [[]]
combs' i xs = [ y:ys | y <- xs, ys <- combs' (i-1) (filter (> y) xs) ]
于 2014-10-12T17:44:18.513 に答える