3

したがって、基本的に、文字列の（有限または無限）リストの（有限または無限）リストがある場合、重複を除いて、最初に長さで、次に辞書式順序でリストを並べ替えることはできますか？サンプルの入力/出力は次のようになります。

入力：

[["a"、 "b"、...]、["a"、 "aa"、 "aaa"]、["b"、 "bb"、 "bbb"、...]、..。 ]

出力：

["a"、 "b"、 "aa"、 "bb"、 "aaa"、 "bbb"、...]

入力リストが有効なhaskell式ではないことは知っていますが、そのような入力があると仮定します。マージアルゴリズムを使用してみましたが、指定した入力にハングする傾向があります。誰かがこれを行うことができるまともなソート機能を説明して示すことができますか？そのような機能がない場合、その理由を説明していただけますか？

ソート順の意味がわからない場合は、最短の長さの文字列が最初にソートされ、1つ以上の文字列が同じ長さの場合は、<演算子を使用してソートされます。

ありがとう！

4

6 に答える 6

15

最終的に、無限リストをソートすることはできません。リストの末尾にあるアイテムが結果の前にずっと浸透する可能性があるためです。したがって、最後のアイテムが表示されるまで無限リストのソートを完了することはできません。しかし、あなたのリストは無限であるため、そこにたどり着くことはありません。

無限リストをソートしようとする唯一の方法は、リストの住民に対する制約を必要とすることです。リスト項目の値が十分に根拠のあるセットから取得され、リストの内容が一意である場合、要素をリストの最初の要素に戻すことで少なくともある程度の進歩を遂げることができます。たとえば、リストが個別の自然数である場合、最初に表示される 0 を返し、次に最初に 1 などを返すことができますが、リストのどこまで行っても、2 が表示されるまで結果を進めることはできませんでした。あなたが行きました。最終的に、ソースに存在しなかったためにセット内の要素をスキップした場合、入力全体を手に入れるまで、新しい出力要素の生成を停止します。

文字列は十分に確立されているため、文字列でも同じことを行うことができますが、可能なすべての文字列を返すことを計画している場合は、リモートでしか実行できません。

つまり、これが必要な場合は、問題を間違った方法で解決しようとしています。これは、使用したいソリューションへの扱いやすいパスではありません。

yairchu が指摘したように、有限数の並べ替えられた無限リストをマージしても問題ありません。

于 2010-03-07T07:25:10.770 に答える
9

  • 一般に、無限リストをソートすることは不可能です。最小のアイテムが無限の位置にある可能性があるため、出力する前にそれを見つけなければなりません。

  • 無限に並べ替えられたリストのマージが可能です。

  • 一般に、ソートされたリストの無限リストをマージすることは不可能です。それらをソートするのと同じ理由で。

  • 見出し ( forall i j. i < j=> head (lists !! i) <= head (lists !! j)) でソートされたソート済みリストの無限リストをマージすることが可能です。

したがって、あなたが本当に望んでいるのは、ソートされたリストのソートされた無限リストをマージすることだと思います。意味のあるタスクですらあります。それを使用する既存のコードもいくつかあり、モナド リスト用に実装されています。

mergeOnSortedHeads :: Ord b => (a -> b) -> [[a]] -> [a]
mergeOnSortedHeads _ [] = []
mergeOnSortedHeads f ([]:xs) = mergeOnSortedHeads f xs
mergeOnSortedHeads f ((x:xs):ys) =
  x : mergeOnSortedHeads f (bury xs ys)
  where
    bury [] ks = ks
    bury js [] = [js]
    bury js ([]:ks) = bury js ks
    bury jj@(j:js) ll@(kk@(k:ks):ls)
      | f j <= f k = jj : ll
      | otherwise = kk : bury jj ls

ghci> take 20 $ mergeOnSortedHeads id $ [[0,4,6], [2,3,9], [3,5..], [8]] ++ map repeat [12..]
[0,2,3,3,4,5,6,7,8,9,9,11,12,12,12,12,12,12,12,12]

ところで：これは何のために必要ですか？

于 2010-03-07T07:23:49.833 に答える
3

そうですね、無限のデータをソートするというあなたのリクエストは無視します。

サブリストの長さで並べ替え、次に辞書順で並べ替えるには、これを非常に簡単に行うことができます。ああ、重複を削除したい。

サンプルから始めます。

> s
[["a","b"],["a","aa","aaa"],["b","bb","bbb"]]

次に、プログラムを段階的にビルドします。

長さによる最初のソート (Data.Ord.comparing を使用してソート本体を作成):

> sortBy (comparing length) s
[["a","b"],["a","aa","aaa"],["b","bb","bbb"]]

Ok。それは合理的に見えます。それでは、concat と、sortBy length の次に alpha を実行しましょう。

> sortBy (comparing length) . nub . concat $ s
["a","b","aa","bb","aaa","bbb"]

入力がソートされている場合。それ以外の場合は、sortBy に少し異なる本体が必要になります。

于 2010-03-07T01:08:17.687 に答える
1

オンラインソートを可能にするアルゴリズムは次のとおりです。

効率的ではありませんが、たとえ無限リストをソートしたとしても、異なるソート世代に移動できるほど怠惰です。いいギミックですが、あまり使い物になりません。たとえば、無限リスト [10,9..] の並べ替え:

*Main> take 10 $ sortingStream [10,9..] !! 0
[9,8,7,6,5,4,3,2,1,0]
*Main> take 10 $ sortingStream [10,9..] !! 1
[8,7,6,5,4,3,2,1,0,-1]
*Main> take 10 $ sortingStream [10,9..] !! 2
[7,6,5,4,3,2,1,0,-1,-2]
*Main> take 10 $ sortingStream [10,9..] !! 3
[6,5,4,3,2,1,0,-1,-2,-3]
*Main> take 10 $ sortingStream [10,9..] !! 4
[5,4,3,2,1,0,-1,-2,-3,-4]
*Main> take 10 $ sortingStream [10,9..] !! 1000
[-991,-992,-993,-994,-995,-996,-997,-998,-999,-1000]

ご覧のとおり、並べ替えは世代ごとに改善されます。コード：

produce :: ([a] -> [a]) -> [a] -> [[a]]
produce f xs = f xs : (produce f (f xs))


sortingStream :: (Ord a) => [a] -> [[a]]
sortingStream = produce ss

ss :: (Ord a) => [a] -> [a]
ss [] = []
ss [x] = [x]
ss [x,y]    | x <= y = [x,y]
            | otherwise = [y,x]
ss (x:y:xs) | x <= y  =  x: (ss (y:xs))
            | otherwise =  y:(ss (x:xs))
于 2010-05-15T02:49:14.550 に答える
1

ご意見をお寄せいただきありがとうございます。返信が遅れて申し訳ありません。私は間違った方法で問題に取り組んでいたことがわかりました。私はYairchuが示したことをやろうとしていましたが、組み込み関数lengthを使用してマージを行っていましたが、明らかな理由で無限リストでは長さが機能しません。とにかく、最終結果ではなく、外出先でリストを作成したときにソートすることで問題を解決しました。無限リストを提供する言語は他にあるでしょうか。そのような奇妙だが便利な概念。

于 2010-03-10T15:40:15.100 に答える
0

それができるかどうかは、入力データの性質に大きく依存します。長いリストを見たときに特定の長さのリストを「探すのをやめる」ことができ、各長さのリストの数が限られている場合は、長さを昇順で調べ、それらを並べ替えて連結することができます結果。このようなものが動作するはずです:

listsUptoLength n xss = takeWhile (\xs -> length xs <= n) $ xss 
listsUptoLength' n [] = []
listsUptoLength' n (xss:xsss) = case listsUptoLength n xss of
    [] -> []
    xss' -> xss' : listsUptoLength' n xsss
listsOfLength n xsss = concatMap (\xss -> (filter (\xs -> length xs == n) xss)) (listsUptoLength' n xsss) 

sortInfinite xsss = concatMap (\n -> sort . nub $ (listsOfLength n xsss)) [0..] 

f xs y = [xs ++ replicate n y | n <- [1..]]
test = [ map (\x -> [x]) ['a'..'e'], f "" 'a', f "" 'b', f "b" 'a', f "a" 'b' ] ++ [f start 'c' | start <- f "" 'a']

(名前はおそらく、より明確になるように選択できます:)

あなたは正規表現を扱っていると思いますので、このようなものを機能させることができると思います。背景のリクエストを繰り返します！

于 2010-03-07T12:29:04.450 に答える