如何生成从最短到最长的所有可能字符串的列表 [英] How to generate a list of all possible strings from shortest to longest

问题描述

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

I need to generate an infinite list of strings using numbers and letters. The first string should simply be "a", then "b" through to "z", then "0" through to "9", then "aa", "ab" etc.

我可以轻松地生成一个字符的字符，但随后变得更加复杂.

I can easily generate the ones with one character, but then it gets more complicated.

推荐答案

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

So, suppose we already had this list of all possible strings:

 allStrings :: [String]
 allStrings = ...

给出allStrings，我们如何创建所有可能字符串的另一个列表?

Given allStrings, how could we create another list of all possible strings?

 alsoAllStrings :: [String]

让我们将每个可能的字符串视为一个字符前缀和一个字符串后缀

Let's look at each possible string as a single character prefix, and a string suffix

 alsoAllStrings = [ c : s 

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

The string suffix is either the empty string or a member of the list of all possible strings.

                  | s <- "" : allStrings

单个字符前缀在'a'至'z'或'0'至'9'中.

The single character prefix is in 'a' thru 'z' or '0' thru '9'.

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

(这是使用列表推导-我们也可以使用concatMap做同样的事情:

(this is using list comprehensions - we could also do the same using concatMap:

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

)

现在让我们回到最初的问题.我们如何找到allStrings?

Now let's go back to the original question. How do we find allStrings?

在大多数语言中，我们不能-它是无限的字符串列表，程序将永远无法完成.但是由于Haskell很懒，因此只生成与我们实际使用的一样多的allStrings很酷.

In most languages, we couldn't - it's an infinite list of strings, the program would never finish. But since Haskell is lazy, it's cool with generating only as much of allStrings as we actually use.

这让我们做的一件令人惊讶的事情是，我们可以用alsoAllStrings来定义allStrings.

One surprising thing that this lets us do is we can define allStrings in terms of alsoAllStrings.

 allStrings = alsoAllStrings

或者更有可能就其本身而言.

Or, more likely, in terms of itself.

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

这称为核心递归数据-根据自身定义的数据. 在ghci中试用:

This is called corecursive data - data that is defined in terms of itself. Try it out in 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元素就越多，并且可用作后缀.

The reason it works (and doesn't just loop infinitely) is that it defines part of itself before it uses itself. The first elements we include in allStrings are the single character extensions to the empty string "". So by the time we start iterating through the elements of allStrings to use as suffixes, the first couple elements allStrings are already defined and available. And the more suffixes we process, the more elements of allStrings are defined and available to use as suffixes.

这与以草草定义斐波那契数的常见haskellism非常相似:

It's very similar to a common haskellism of defining the fibonacci numbers corecursively:

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

如果corecursion花费一些时间将您的头缠起来，请不要感到惊讶.不过，值得努力去理解.

Don't be surprised if corecursion takes a while to wrap your head around. It's worth the effort to understand, though.

这篇关于如何生成从最短到最长的所有可能字符串的列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！