如何生成从最短到最长的所有可能字符串的列表

Question

我需要使用数字和字母生成无限的字符串列表.第一个字符串应该只是"a",然后是"b"到"z",然后是"0"到"9",然后是"aa","ab"等.

我可以很容易地生成具有一个字符的那些,但随后它变得更复杂.

Answer 1

所以,假设我们已经有了所有可能字符串的列表:

 allStrings :: [String]
 allStrings = ...

鉴于allStrings,我们如何创建所有可能字符串的另一个列表？

 alsoAllStrings :: [String]

让我们将每个可能的字符串看作单个字符前缀和字符串后缀

 alsoAllStrings = [ c : s 

字符串后缀是空字符串或所有可能字符串列表的成员.

                  | s <- "" : allStrings

单个字符前缀是'a'直通'z'或'0'直通'9'.

                  , c <- ['a'..'z'] ++ ['0'..'9']
                  ]

(这是使用列表推导 - 我们也可以使用concatMap:

alsoAllStrings = concatMap (\s -> map (:s) $ ['a'..'z'] ++ ['0'..'9']) $ "" : allStrings

)

现在让我们回到最初的问题.我们怎么找到allStrings？

在大多数语言中,我们不能 - 它是一个无限的字符串列表,程序永远不会完成.但是因为Haskell很懒,所以只产生allStrings我们实际使用的那么多很酷.

一个令人惊讶的事情,这让我们做的是我们可以定义allStrings来讲alsoAllStrings.

 allStrings = alsoAllStrings

或者,更可能的是,就其本身而言.

 allStrings = [ c : s | s <- "" : allStrings, c <- ['a'..'z'] ++ ['0'..'9'] ]

这称为corecursive数据 - 根据自身定义的数据.在ghci中尝试一下:

 ghci> let allStrings = [ c : s | s <- "": allStrings, c <- ['a'..'z'] ++ ['0'..'9'] ]
 ghci> take 100 allStrings
 ["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z","0","1","2","3","4","5","6","7","8","9","aa","ba","ca","da","ea","fa","ga","ha","ia","ja","ka","la","ma","na","oa","pa","qa","ra","sa","ta","ua","va","wa","xa","ya","za","0a","1a","2a","3a","4a","5a","6a","7a","8a","9a","ab","bb","cb","db","eb","fb","gb","hb","ib","jb","kb","lb","mb","nb","ob","pb","qb","rb","sb","tb","ub","vb","wb","xb","yb","zb","0b","1b"]

它工作的原因(并不仅仅是无限循环)是它在使用自身之前定义了它自身的一部分.我们包含的第一个元素allStrings是空字符串的单个字符扩展"".因此,当我们开始迭代allStrings使用后缀的元素时,前几个元素allStrings已经定义并可用.我们处理的后缀越多,allStrings定义的元素就越多,可以用作后缀.

它非常类似于共同定义斐波纳契数的常见问题:

 fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

如果corecursion需要一段时间来包裹你的头,请不要感到惊讶.不过,值得努力去理解.

Answer 2

这可以通过获取长度为1,2,3 ...的字符串的所有组合来完成,然后将它们全部合并在一起.

我从一个组合函数开始,它返回给定字符和给定长度的所有字符串列表:

combos :: [Char] -> Int -> [String]

第一种情况很简单,只需将输入字符转换为列表:

combos chars 1 = map (:[]) chars

下一个案例我们想要'aa','ab','ac'......到'zx','zy','zz'.这和map ("a" ++) ["a", "b", "c"...] ++ map ("b" ++) ["a","b",...]以前一样map ("z" ++) ["a","b"...].

["a".."z"]是一样的combos chars 1.该功能可写为:

combos chars 2 = concatMap (\front -> map (front ++) (combos chars 1)) (combos chars 1)

下一个案例我们想要'aaa','aab',......'zzy','zzz'.这实际上非常类似于组合2,除了我们用作前面combos chars 2而不是combos chars 1:

combos chars 3 = concatMap (\front -> map (front ++) (combos chars 1)) (combos chars 2)

(注意combos chars 1不会改变,只是给我们一个字符串的列表附加到末尾.)

看到这里的模式？现在可以将所有n推广为:

combos :: [Char] -> Int -> [String]
combos chars 1 = map (:[]) chars
combos chars n = concatMap (\front -> map (front ++) (combos chars 1)) $ combos chars (n - 1)

最后,要获得所有字符串的无限列表,只需将所有组合结果与所需字符和所有长度连接起来:

allCombos :: [String]
allCombos = concatMap (combos (['a'..'z'] ++ ['0'..'9'])) [1..]

示例输出:

> take 100 allCombos
["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z","0","1","2","3","4","5","6","7","8","9","aa","ab","ac","ad","ae","af","ag","ah","ai","aj","ak","al","am","an","ao","ap","aq","ar","as","at","au","av","aw","ax","ay","az","a0","a1","a2","a3","a4","a5","a6","a7","a8","a9","ba","bb","bc","bd","be","bf","bg","bh","bi","bj","bk","bl","bm","bn","bo","bp","bq","br","bs","bt","bu","bv","bw","bx","by","bz","b0","b1"]