Factorial base numbers indexing permutations of a collection: Difference between revisions

=={{header|Haskell}}==

Factoradic representation of integer numbers in canonical form (with trailing zero).

<lang haskell>import Data.List (unfoldr, intercalate)

newtype Fact = Fact [Int]

-- smart constructor

fact :: [Int] -> Fact

fact = Fact . zipWith min [0..] . reverse

instance Show Fact where

show (Fact ds) = intercalate "." $ show <$> reverse ds

toFact :: Integer -> Fact

toFact 0 = Fact [0]

toFact n = Fact $ unfoldr f (1, n)

where

f (b, 0) = Nothing

f (b, n) = let (q, r) = n `divMod` b

in Just (fromIntegral r, (b+1, q))

fromFact :: Fact -> Integer

fromFact (Fact ds) = foldr f 0 $ zip [1..] ds

where

f (b, d) r = r * b + fromIntegral d</lang>

<pre>λ> toFact 2021

2.4.4.0.2.1.0

λ> fromFact it

2021

λ> fact [2,2,1,0]

2.2.1.0</pre>

Correspondence with permutations:

<lang haskell>toPermutation :: Fact -> [Int]

toPermutation (Fact ds) = go (reverse ds) [0.. length ds - 1]

where

go [] p = p

go (d:ds) p = case splitAt (fromIntegral d) p of

(a,x:b) -> x : go ds (a++b)

(a,[]) -> a

permute :: [a] -> [Int] -> [a]

permute s p = case splitAt (length s - length p) s of

(s1,s2) -> s1 ++ map (s2 !!) p</lang>

<pre>λ> toPermutation (fact [4,0,2,1,0])

[4,0,3,2,1]

λ> permute "abcde" $ toPermutation (fact [4,0,2,1,0])

"eadcb"

λ> permute "abcdefgh" $ toPermutation (fact [4,0,2,1,0])

"abchdgfe"</pre>

Given tasks

<lang haskell>task1 = do

putStrLn "number\tfactoradic\tpermutation"

mapM_ display [0..23]

where

display n =

let f = toFact n

p = permute "0123" (toPermutation f)

in putStrLn $ show n ++ "\t" ++ show f ++ "\t\t(" ++ p ++ ")"

randomFactDigits seed = zipWith mod (random seed) [1..]

where

random = iterate $ \x -> (x * 1103515245 + 12345) `mod` (2^31-1)

task2 = do

putStrLn "-- First example --"

let n1 = toFact 61988771037597375208735783409763169805823569176280269403732950003152

let crate1 = permute crate $ toPermutation n1

putStrLn $ "Factoradic number:\n" ++ show n1

putStrLn $ "Corresponding crate permutation:\n" ++ unwords crate1

putStrLn "\n-- Second example --"

let n2 = toFact 80576939285541005152259046665383499297948014296200417968998877609223

let crate2 = permute crate $ toPermutation n2

putStrLn $ "Factoradic number:\n" ++ show n2

putStrLn $ "Corresponding crate permutation:\n" ++ unwords crate2

putStrLn "\n-- Random example --"

let n3 = Fact $ take 52 $ randomFactDigits 42

let crate3 = permute crate $ toPermutation n3

putStrLn $ "Factoradic number:\n" ++ show n3

putStrLn $ "Decimal representation of n:\n" ++ show (fromFact n3)

putStrLn $ "Corresponding crate permutation:\n" ++ unwords crate3

where

crate = words "A♠ K♠ Q♠ J♠ 10♠ 9♠ 8♠ 7♠ 6♠ 5♠ 4♠ 3♠ 2♠\

\ A♥ K♥ Q♥ J♥ 10♥ 9♥ 8♥ 7♥ 6♥ 5♥ 4♥ 3♥ 2♥\

\ A♦ K♦ Q♦ J♦ 10♦ 9♦ 8♦ 7♦ 6♦ 5♦ 4♦ 3♦ 2♦\

\ A♣ K♣ Q♣ J♣ 10♣ 9♣ 8♣ 7♣ 6♣ 5♣ 4♣ 3♣ 2♣"</lang>

<pre>λ> task1

number factoradic permutation

0 0 (0123)

1 1.0 (0132)

2 1.0.0 (0213)

3 1.1.0 (0231)

4 2.0.0 (0312)

5 2.1.0 (0321)

6 1.0.0.0 (1023)

7 1.0.1.0 (1032)

8 1.1.0.0 (1203)

9 1.1.1.0 (1230)

10 1.2.0.0 (1302)

11 1.2.1.0 (1320)

12 2.0.0.0 (2013)

13 2.0.1.0 (2031)

14 2.1.0.0 (2103)

15 2.1.1.0 (2130)

16 2.2.0.0 (2301)

17 2.2.1.0 (2310)

18 3.0.0.0 (3012)

19 3.0.1.0 (3021)

20 3.1.0.0 (3102)

21 3.1.1.0 (3120)

22 3.2.0.0 (3201)

23 3.2.1.0 (3210)

λ> task2

-- First example --

Factoradic number:

39.49.7.47.29.30.2.12.10.3.29.37.33.17.12.31.29.34.17.25.2.4.25.4.1.14.20.6.21.18.1.1.1.4.0.5.15.12.4.3.10.10.9.1.6.5.5.3.0.0.0.0

Corresponding crate permutation:

A♣ 3♣ 7♠ 4♣ 10♦ 8♦ Q♠ K♥ 2♠ 10♠ 4♦ 7♣ J♣ 5♥ 10♥ 10♣ K♣ 2♣ 3♥ 5♦ J♠ 6♠ Q♣ 5♠ K♠ A♦ 3♦ Q♥ 8♣ 6♦ 9♠ 8♠ 4♠ 9♥ A♠ 6♥ 5♣ 2♦ 7♥ 8♥ 9♣ 6♣ 7♦ A♥ J♦ Q♦ 9♦ 2♥ 3♠ J♥ 4♥ K♦

-- Second example --

Factoradic number:

51.48.16.22.3.0.19.34.29.1.36.30.12.32.12.29.30.26.14.21.8.12.1.3.10.4.7.17.6.21.8.12.15.15.13.15.7.3.12.11.9.5.5.6.6.3.4.0.3.2.1.0

Corresponding crate permutation:

2♣ 5♣ J♥ 4♥ J♠ A♠ 5♥ A♣ 6♦ Q♠ 9♣ 3♦ Q♥ J♣ 10♥ K♣ 10♣ 5♦ 7♥ 10♦ 3♠ 8♥ 10♠ 7♠ 6♥ 5♠ K♥ 4♦ A♥ 4♣ 2♥ 9♦ Q♣ 8♣ 7♦ 6♣ 3♥ 6♠ 7♣ 2♦ J♦ 9♥ A♦ Q♦ 8♦ 4♠ K♦ K♠ 3♣ 2♠ 8♠ 9♠

-- Random example --

Factoradic number:

25.36.42.26.5.9.25.5.38.24.30.19.37.7.5.20.35.28.32.6.22.19.20.14.9.5.21.23.9.22.15.10.10.17.7.8.4.14.8.2.3.8.7.6.2.0.4.2.1.2.0.0

Decimal representation of n:

39898748133187068184262739663110406401085629856403860440579024763898

Corresponding crate permutation:

2♥ 3♦ 9♣ K♦ 9♠ 4♠ J♦ 8♠ 7♣ 10♦ 2♦ 5♥ 4♣ 5♠ 7♠ Q♦ 2♣ Q♣ 5♣ 3♠ 6♦ 9♦ 7♦ 7♥ Q♥ 6♠ J♣ 6♣ 10♥ 3♣ 8♦ 8♥ 6♥ 10♣ K♥ 9♥ 10♠ 8♣ 3♥ Q♠ 2♠ 4♦ 5♦ A♦ J♠ A♠ A♣ J♥ A♥ K♣ K♠ 4♥</pre>