2

単一の文字列から可能なすべての部分文字列をどのように抽出しますか? 私は一種の面倒な方法を思いついたので、もっと簡単な方法を見つけたいと思っています。

subStrings :: String -> [String]
subStrings xs = xs : takeEl xs

takeEl :: String -> [String]
takeEl xs = nub (concat [y : (takeEl y) | y <- takeEl'])
  where 
    takeEl' = [del y xs | y <- [0..(length xs - 1)]]

del :: Int -> [a] -> [a]
del k xs = take k xs ++ drop (k+1) xs

例を挙げてもう少し説明したいと思います。「abc」で関数を使用する場合、順列なしで以下の要素を含むリストを作成する必要があります (「ab」が存在する場合、「ba」は必要ありません) ）。

`["abc", "a","b","c","ab","ac","bc",""]`

したがって、 inits を連結します。それは私に「ac」を与えないので、尾は十分ではありません.

4

5 に答える 5

5

このData.Listモジュールはsubsequences、これの正しい名前であるを提供しています。(部分文字列は連続しています。)

于 2013-10-22T22:30:47.147 に答える
3

編集:以下は、 subsequencesではなく、元の質問で言及されたsubstringsを 計算します。

何か手っ取り早いものを探している場合 (そして、必ずしもできるだけ効率的であるとは限りません)、私が提案するのは次のとおりです。

import Data.List (inits, tails)

nonEmptySubstrings :: [a] -> [[a]]
nonEmptySubstrings = concatMap (tail . inits) . tails

空のtail部分文字列を完全に削除するには、 が必要です。そうしないと、複数回発生します。それも必要な場合は、追加する必要があります。

substrings :: [a] -> [[a]]
substrings = ([] :) . nonEmptySubstrings

例：

Prelude Data.List> nonEmptySubstrings "abcd"
["a","ab","abc","abcd","b","bc","bcd","c","cd","d"]
Prelude Data.List> substrings "abcd"
["","a","ab","abc","abcd","b","bc","bcd","c","cd","d"]
于 2013-10-22T18:08:08.893 に答える
1

あなたが求めているのは、すべてのサブシーケンスのリストではなく、すべてのサブセットのリスト (元の順序を維持) -パワー セットのようです。これは、リストモナドの素敵なトリックで実現できます:

filterM (const [False, True]) "abc"

収量

["","c","b","bc","a","ac","ab","abc"]

秘訣は、リスト モナド内の指定されたリストを非決定論的にフィルタリングし、特定の要素を保持および削除するように分岐することです。

于 2014-02-07T19:44:16.710 に答える