次のように、2 つ (または 3 つ) の無限リストを繰り返し、条件を満たす「最小」のペアを見つけたいと考えています。
until pred [(a,b,c) | a<-as, b<-bs, c<-cs]
where pred (a,b,c) = a*a + b*b == c*c
as = [1..]
bs = [1..]
cs = [1..]
上記は a == b == 1、プログラムの実行中ずっと、それほど遠くまでは行きません。たとえば、無限シーケンスを構築するなど、問題を一致させる良い方法はあります[(1,1,1),(1,2,1),(2,1,1),(2,1,2),(2,2,1),(2,2,2),(2,2,3),(2,3,2),..]か?
ボーナス: n タプルに一般化することは可能ですか?
そのためのモナド、Omegaがあります。
Prelude> let as = each [1..]
Prelude> let x = liftA3 (,,) as as as
Prelude> let x' = mfilter (\(a,b,c) -> a*a + b*b == c*c) x
Prelude> take 10 $ runOmega x'
[(3,4,5),(4,3,5),(6,8,10),(8,6,10),(5,12,13),(12,5,13),(9,12,15),(12,9,15),(8,15,17),(15,8,17)]
その応用機能を使用して、任意のタプルに一般化できます。
quadrupels = (,,,) <$> as <*> as <*> as <*> as -- or call it liftA4
しかし、もちろん、これだけでは重複をなくすことはできません。それはあなたに適切な対角化を与えるだけです。たぶん、モナド内包表記を Thomas のようなアプローチや、別のmfilterパス (b /= cこの場合は に制限)と一緒に使用できます。
リスト内包表記は、このような問題を解決する優れた (そして簡潔な) 方法です。(a,b,c)まず、満足する可能性のあるのすべての組み合わせが必要であることを知ってa^2 + b^2 = c^2います。有益な観察は、(正の数のみを考慮して)常にa <= c && b <= c.
候補のリストを生成するために、c範囲は1から無限大までa、b範囲は 1 から までcです。
[(a,b,c) | c <- [1..], a <- [1..c], b <- [1..c]]
ソリューションにたどり着くには、必要な方程式をガードとして追加する必要があります。
[(a,b,c) | c <- [1..], a <- [1..c], b <- [1..c], a*a+b*b == c*c]
これは非効率的ですが、出力は正しいです:
[(3,4,5),(4,3,5),(6,8,10),(8,6,10),(5,12,13),(12,5,13),(9,12,15)...
この問題を解決できるブラインドテストよりも原理的な方法があります。
{-「最小」とは何かによって異なります。ただし、タプルが最初に最大値で比較された場合の「最小」の概念の解決策は次のとおりです。数、次にそれらの合計。（コメントにテキストを書いているので、回答全体をコピーしてファイルに貼り付けることができます。）
後で必要nubになります。-}
import Data.List (nub)
{- 説明用: 2 タプルの簡単なケース。-}
-- all the two-tuples where 'snd' is 'n'
tuples n = [(i, n) | i <- [1..n]]
-- all the two-tuples where 'snd' is in '1..n'
tuplesUpTo n = concat [tuples i | i <- [1..n]]
{- すべての結果を取得するには、各タプルのフリップをストリームに挿入する必要があります。しかし、それは後で行い、最初に一般化しましょう。
任意の長さのタプルを構築するのはやや難しいので、リストで作業します。長さが「k」の場合、それらを「kList」と呼びます。-}
-- just copied from the tuples case, only we need a base case for k=1 and
-- we can combine all results utilizing the list monad.
kLists 1 n = [[n]]
kLists k n = do
rest <- kLists (k-1) n
add <- [1..head rest]
return (add:rest)
-- same as above. all the klists with length k and max number of n
kListsUpTo k n = concat [kLists k i | i <- [1..n]]
-- we can do that unbounded as well, creating an infinite list.
kListsInf k = concat [kLists k i | i <- [1..]]
{- 次のステップは、これらのリストをローテーションすることです。これまでは、最大数が常に最後にあったためです。したがって、すべての結果を取得するためにすべての回転を調べるだけです。ここでの使用nub は確かに扱いにくいですが、改善することができます。しかし、それがなければ、すべての要素が同じリストは何k度も繰り返されます。-}
rotate n l = let (init, end) = splitAt n l
in end ++ init
rotations k l = nub [rotate i l | i <- [0..k-1]]
rotatedKListsInf k = concatMap (rotations k) $ kListsInf k
{- 残っているのは、これらのリストをタプルに変換することです。すべての n タプルが個別の型であるため、これは少し厄介です。しかし、それはもちろん簡単です。-}
kListToTuple2 [x,y] = (x,y)
kListToTuple3 [x,y,z] = (x,y,z)
kListToTuple4 [x,y,z,t] = (x,y,z,t)
kListToTuple5 [x,y,z,t,u] = (x,y,z,t,u)
kListToTuple6 [x,y,z,t,u,v] = (x,y,z,t,u,v)
{- いくつかのテスト:
*Main> take 30 . map kListToTuple2 $ rotatedKListsInf 2
[(1,1),(1,2),(2,1),(2,2),(1,3),(3,1),(2,3),(3,2),(3,3),(1,4),(4,1),(2,4),(4,2),(3,4),
(4,3),(4,4),(1,5),(5,1),(2,5),(5,2),(3,5),(5,3),(4,5),(5,4),(5,5),(1,6),(6,1),
(2,6), (6,2), (3,6)]
*Main> take 30 . map kListToTuple3 $ rotatedKListsInf 3
[(1,1,1),(1,1,2),(1,2,1),(2,1,1),(1,2,2),(2,2,1),(2,1,2),(2,2,2),(1,1,3),(1,3,1),
(3,1,1),(1,2,3),(2,3,1),(3,1,2),(2,2,3),(2,3,2),(3,2,2),(1,3,3),(3,3,1),(3,1,3),
(2,3,3),(3,3,2),(3,2,3),(3,3,3),(1,1,4),(1,4,1),(4,1,1),(1,2,4),(2,4,1),(4,1,2)]
編集: バグがあることに気付きました:もちろん、順序付きリストを回転させるだけでは十分ではありません。解決策は、
rest <- concat . map (rotations (k-1)) $ kLists (k-1) n
でkLists、しかしその後、出力の繰り返しに関するいくつかの問題が発生します。あなたはそれを理解できると思います。;-) -}
それは本当に「最小」の意味に依存しますが、最大要素に関して数値のタプルを見つけたいと思います-そう(2,2)です(1,3)（標準のHaskell順序付けは辞書式です）。
パッケージdata-ordlistがあります。これは、順序付きリストを操作することを正確に目的としています。その関数mergeAll(およびmergeAllBy) を使用すると、各方向に並べられた 2 次元行列を順序付けられたリストに結合できます。
まず、タプルで必要な比較関数を作成しましょう。
import Data.List (find)
import Data.List.Ordered
compare2 :: (Ord a) => (a, a) -> (a, a) -> Ordering
compare2 x y = compare (max2 x, x) (max2 y, y)
where
max2 :: Ord a => (a, a) -> a
max2 (x, y) = max x y
次に、 を使用しmergeAllて、コンパレータ、結合関数 (両方の引数で単調でなければなりません)、および 2 つの並べ替えられたリストを受け取る関数を作成します。関数を使用して 2 つのリストから可能なすべての要素を結合し、結果の並べ替えられたリストを生成します。
mergeWith :: (b -> b -> Ordering) -> (a -> a -> b) -> [a] -> [a] -> [b]
mergeWith cmp f xs ys = mergeAllBy cmp $ map (\x -> map (f x) xs) ys
この関数を使用すると、最大値に従って順序付けされたタプルを生成するのは非常に簡単です。
incPairs :: [(Int,Int)]
incPairs = mergeWith compare2 (,) [1..] [1..]
その最初の 10 個の要素は次のとおりです。
> take 10 incPairs
[(1,1),(1,2),(2,1),(2,2),(1,3),(2,3),(3,1),(3,2),(3,3),(1,4)]
そして、(たとえば) 二乗和が 65 に等しい最初のペアを探すと、次のようになります。
find (\(x,y) -> x^2+y^2 == 65) incPairs
(辞書式順序が使用された場合(4,7)とは対照的に)正しい結果が得られます。(1,8)
この回答は、未知の述語に関するより一般的な問題に対するものです。述語がわかっている場合は、特定の c のすべての Int を反復する必要がないという知識に基づいて他の人がソリューションをリストしたように、より効率的なソリューションが可能です。
無限リストを扱うときは、幅優先探索を実行して解を求める必要があります。リスト内包表記は深さ優先検索のみを提供するため、元のコードで解決策に到達することはありません。
counters 0 xs = [[]]
counters n xs = concat $ foldr f [] gens where
gens = [[x:t | t <- counters (n-1) xs] | x <- xs]
f ys n = cat ys ([]:n)
cat (y:ys) (x:xs) = (y:x): cat ys xs
cat [] xs = xs
cat xs [] = [xs]
main = print $ take 10 $ filter p $ counters 3 [1..] where
p [a,b,c] = a*a + b*b == c*c
counters無限の範囲を含む、指定された範囲の桁からの値に対して可能なすべてのカウンターを生成します。
最初に、カウンターの有効な組み合わせのジェネレーターのリストを取得します。許可された数字ごとに、それをより小さいサイズのカウンターの許可されたすべての組み合わせと組み合わせます。これにより、無限の数の組み合わせを生成するジェネレーターが生成される場合があります。したがって、各ジェネレーターから均等に借用する必要があります。
ジェネレーターgensのリストも同様です。これは、1 桁で始まるすべてのカウンターのリストと考えてください。は で始まるすべてのカウンターのリスト、は でgens !! 0始まるすべてのカウンターのリスト、などです。1gens !! 12
各ジェネレーターから均等に借用するために、ジェネレーターのリストを転置することができます。このようにして、ジェネレーターの最初の要素のリストを取得し、その後にジェネレーターの 2 番目の要素のリストを取得します。
ジェネレーターのリストは無限になる可能性があるため、ジェネレーターのリストを転置する余裕はありません。これは、ジェネレーターの 2 番目の要素を確認できない可能性があるためです (桁数が無限の場合、ジェネレーターの数は無限になります)。 . したがって、ジェネレーターからの要素を「斜めに」列挙します。最初のジェネレーターから最初の要素を取得します。次に、最初のジェネレーターから 2 番目の要素を取得し、2 番目のジェネレーターから最初の要素を取得します。次に、最初のジェネレーターから 3 番目の要素を取得し、2 番目のジェネレーターから 2 番目の要素を取得し、3 番目のジェネレーターから 1 番目の要素を取得しますf。ジェネレーター、もう 1 つは圧縮済みのジェネレーターです。[]:頭に。これはほとんどですzipWith (:) ys ([]:n)- 違いは、n または ys が他のリストよりも短い場合、他のリストの残りを削除しないことです。で折りたたむとzipWith (:) ys n転置になることに注意してください。
「最小」が x+y+z として定義されている場合、これが最も単純なソリューションだと思います。これは、整数値のピタゴラス三角形の空間で最初のソリューションを見つけた後、無限リストからの次のソリューションが大きくなるためです。
take 1 [(x,y,z) | y <- [1..], x <- [1..y], z <- [1..x], z*z + x*x == y*y]
-> [(4,5,3)]
対称的に一意の各ソリューションを一度だけ返すという優れた特性があります。y が無限であるため、x と z も無限です。
x のシーケンスが終了しないため、これは機能しません。したがって、z は言うまでもなく、y の値も得られません。右端のジェネレーターは、最も内側のループです。
take 1 [(z,y,x)|z <- [1..],y <- [1..],x <- [1..],x*x + y*y == z*z]
すみません、haskellをやったのはかなり久しぶりなので、言葉で説明します。
私のコメントで指摘したように。無限のリストには常に小さいものが存在する可能性があるため、最小のものを見つけることはできません。
あなたができることは、リストを取り、「有効な」要素のみ、つまり条件が満たされたリストを返すストリームベースのアプローチを持つことです。この関数を呼び出しましょうtriangle
次に、三角形のリストをある程度計算し、take n (triangle ...)このn要素から最小値を見つけることができます。