Как создать список всех возможных строк от самой короткой до самой длинной

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 data - данные, которые определяются в терминах самих себя.Попробуйте это в 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"]

Answer 3

Я придумал следующее решение:

-- Gives us the concatenated cartesian product of two lists of strings
strCartProd :: [String] -> [String] -> [String]
strCartProd xs ys = [x ++ y | x <- xs, y <- ys]

-- Create initial list of strings (map chars to 1-char strings)
s :: [String]
s = map (:[]) $ ['a'..'z'] ++ ['0'..'9']

-- Iterate and concatenate the resulting lists
result :: [String]
result = id =<< iterate (strCartProd s) [""]

Answer 4

Это можно сделать просто с помощью предопределенной функции replicateM из (Control.Monad).

string = concatMap (\n -> replicateM n (['a'..'z']++['0'..'9'])) [1..]