Create the next lexicographic string in Haskell

Question

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

What I tried:

I tried to create a complete (infinite) list of possible combinations and get the required (next) line of this line, but it is not surprising that it is so slow that I do not even get an answer for N = 6.

I used a 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 noob)

So my question is: how can I do this? If several methods exist, a comparison between them is greatly appreciated. Thanks!

Answer 1

Here's a version with a basic conversion (this way you can add and subtract arbitrarily if you want):

 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 t .d. and inverse g .

Then incrementString = f . succ . g incrementString = f . succ . g

Note. I skipped f implementation for training

Update

for another approach, you can define an increment with the transport 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 simply uses pattern matching to see if the line starts with z and adds an additional a .

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