sux.hs

module Sux where

import Data.List

sux :: Ord a => [a] -> Maybe [a]
sux ns = sux' ns []

sux' :: Ord a => [a] -> [a] -> Maybe [a]
sux' pfx sfx 
  | canInc sfx = Just $ pfx ++ (inc sfx)
  | null pfx = Nothing
  | otherwise = sux' pfx' sfx'
      where (pfx', sfx') = pfx << sfx

inc :: Ord a => [a] -> [a]
inc (n:ns) = m : rest
  where (highers, lowers) = partition (> n) ns
        m:ms = sort highers
        rest = sort $ ms ++ [n] ++ lowers

canInc :: Ord a => [a] -> Bool
canInc = not . descending
  where descending ns = reverse ns == sort ns

(<<) :: [a] -> [a] -> ([a], [a])
as << bs = (as', bs')
  where as' = init as
        bs' = (last as):bs

input = [392, 396, 400, 406, 422, 436, 446, 448, 450, 454, 462, 470, 478, 488, 490, 508, 512, 518, 526, 528, 532, 538, 548, 562, 570, 580, 592, 594, 596, 598, 600, 604, 608, 614, 620, 626, 632, 640]
diffs = input.each_cons(2).map { |a,b| (a-b).abs }

average = diffs.reduce(:+) / diffs.length

result  = [[]]
input.each_with_index do |val,i|
    result.last << val
    if rand(diffs[i]) >= rand(average)
        result << []
    end
end

result = result.select { |ar| ! ar.empty? }
p result

class Succ

    def succ(n)
        ar = n_to_array(n)
        bag = [ar.pop]
        succ1(ar, bag).join.to_i
    end

    private

    def succ1(head, bag)
        return bag if head.empty?
        x = head.pop        
        min = bag.select { |n| n > x } . min
        if min
            head << bag.delete(min) 
            bag << x
            return head + bag.sort
        end
        bag.unshift x
        succ1(head,bag)
    end

    def n_to_array(n)
        s = n.to_s
        ar = s.chars.map { |c| c.to_i }
        ar
    end
end

s = Succ.new
p s.succ(13452)