Next highest int from digits: Difference between revisions

Defining a list of all (if any) digit-shuffle successors of a positive integer,

in terms of permutations.

Or alternatively, defining a lazily-evaluated list of all digit-shuffle successors, this time in terms of minimal digit swaps (rather than the full set of permutations).

(The digit-swap approach makes it feasible to obtain successors of this kind for much larger numbers)

<lang haskell>import Data.List (unfoldr)

digitShuffleSuccessors

:: Integral b

=> b -> [b]

digitShuffleSuccessors n =

let nextDigitPattern = minimalSwap . splitBy (>)

in unDigits <$>

unfoldr

(\ds ->

if null ds

then Nothing

else Just (ds, (nextDigitPattern . reverse) ds))

(nextDigitPattern (reversedDigits n))

minimalSwap

:: Ord a

=> ([a], [a]) -> [a]

minimalSwap ([], x:y:xs) = reverse (y : x : xs)

minimalSwap ([], xs) = []

minimalSwap (_, []) = []

minimalSwap (reversedSuffix, pivot:prefix) =

let (less, h:more) = break (> pivot) reversedSuffix

in reverse (h : prefix) ++ less ++ pivot : more

---------------------------TEST----------------------------

main :: IO ()

main = do

putStrLn $

fTable

"Taking up to 5 digit-shuffle successors of a positive integer:\n"

show

(\xs ->

let harvest = take 5 xs

in rjust

12

' '

(show (length harvest) ++ " of " ++ show (length xs) ++ ": ") ++

show harvest)

digitShuffleSuccessors

[0, 9, 12, 21, 12453, 738440, 45072010, 95322020]

putStrLn $

fTable

"Taking up to 10 digit-shuffle successors of a larger integer:\n"

show

(('\n' :) . unlines . fmap ((" " ++) . show))

(take 10 . digitShuffleSuccessors)

[9589776899767587796600]

--------------------------GENERIC--------------------------

reversedDigits

:: Integral a

=> a -> [a]

reversedDigits 0 = [0]

reversedDigits n = go n

where

go 0 = []

go x = rem x 10 : go (quot x 10)

splitBy :: (a -> a -> Bool) -> [a] -> ([a], [a])

splitBy f xs = go $ break (uncurry f) $ zip xs (tail xs)

where

go (ys, zs)

| null ys = ([], xs)

| null zs = (xs, [])

| otherwise = (fst (head ys) : map snd ys, map snd zs)

unDigits

:: (Foldable t, Num a)

=> t a -> a

unDigits = foldl (\a b -> 10 * a + b) 0

--------------------------DISPLAY--------------------------

fTable :: String -> (a -> String) -> (b -> String) -> (a -> b) -> [a] -> String

fTable s xShow fxShow f xs =

unlines $

s : fmap (((++) . rjust w ' ' . xShow) <*> ((" -> " ++) . fxShow . f)) xs

where

w = maximum (length . xShow <$> xs)

rjust :: Int -> Char -> String -> String

rjust n c = drop . length <*> (replicate n c ++)</lang>

{{Out}}

<pre>Taking up to 5 digit-shuffle successors of a positive integer:

0 -> 0 of 0: []

9 -> 0 of 0: []

12 -> 1 of 1: [21]

21 -> 0 of 0: []

12453 -> 5 of 116: [12534,12543,13245,13254,13425]

738440 -> 5 of 96: [740348,740384,740438,740483,740834]

45072010 -> 5 of 1861: [45072100,45100027,45100072,45100207,45100270]

95322020 -> 1 of 1: [95322200]

Taking up to 10 digit-shuffle successors of a larger integer:

9589776899767587796600 ->

9589776899767587900667

9589776899767587900676

9589776899767587900766

9589776899767587906067

9589776899767587906076

9589776899767587906607

9589776899767587906670

9589776899767587906706

9589776899767587906760</pre>