Generate next lexicographical string in Haskell

Question

If I was given a string like skhfbvqa, how would I generate the next string? For this example, it would be skhfbvqb, and the next string of that would be skhfbvqc, and so on. The given string (and the answer) will always be N characters long (in this case, N=8).

What I tried:

I tried to generate the entire (infinite) list of possible combinations, and get the required (next) string of the given string, but unsurprisingly, it's so slow, that I don't even get the answer for N=6.

I used list comprehension:

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

main = do
    input <- readFile "k.in"
    putStrLn . head . tail . dropWhile (not . (==) input) . map reverse $ allStrings

(Please excuse my incredibly bad Haskell-ing :) Still a noob)

So my question is, how can I do this? If there are multiple methods, a comparison between them is much appreciated. Thanks!

Answer 1

Here's a version with base conversion (this way you could add and subtract arbitrarily if you like):

encode x base = encode' x [] where
  encode' x' z | x' == 0 = z
               | otherwise = encode' (div x' base) ((mod x' base):z)

decode num base =
  fst $ foldr (\a (b,i) -> (b + a * base^i,i + 1)) (0,0) num

Output:

*Main> map (\x -> toEnum (x + 97)::Char) 
       $ encode (decode (map (\x -> fromEnum x - 97) "skhfbvqa") 26 + 1) 26

"skhfbvqb"

Answer 2

I would go and make a helper function f :: Integer -> String and one g :: String -> Integer, where f 1 = "a", ... f 27 = "aa", f 28 = "ab" and so on and the inverse g.

Then incrementString = f . succ . g

Note: I omitted the implementation of f on purpose for learning

Update

for a different approach you could define a increment with carry function inc' :: Char -> (Char, Bool), and then

incString :: String -> String
incString = reverse . incString'
   where incString' [] = []
         incString' (x:xs) = case inc' x of (x',True) -> x': incString' xs
                                            (x',False) -> x':xs

Note: this function is not tail recursive!

Answer 3

I found this to work. It just uses pattern matching to see if the string begins with a z and adds an additional a accordingly.

incrementString' :: String -> String
incrementString' []          = ['a']
incrementString' ('z':xs)    = 'a' : incrementString' xs
incrementString' (x:xs)      = succ x : xs

incrementString :: String -> String
incrementString = reverse . incrementString' . reverse