Anonymous user
Index finite lists of positive integers: Difference between revisions
Index finite lists of positive integers (view source)
Revision as of 09:08, 18 November 2021
, 2 years ago→{{header|Haskell}}: added solution
Alextretyak (talk | contribs) (Added 11l) |
(→{{header|Haskell}}: added solution) |
||
Line 353:
Rank: 1 unrank not bijective
</pre>
=={{header|Haskell}}==
<lang haskell>import Data.List
toBase :: Int -> Integer -> [Int]
toBase b = unfoldr f
where
f 0 = Nothing
f n = let (q, r) = n `divMod` fromIntegral b in Just (fromIntegral r, q)
fromBase :: Int -> [Int] -> Integer
fromBase n lst = foldr (\x r -> fromIntegral n*r + fromIntegral x) 0 lst
------------------------------------------------------------
listToInt :: Int -> [Int] -> Integer
listToInt b lst = fromBase (b+1) $ concat seq
where
seq = [ let (q, r) = divMod n b
in replicate q 0 ++ [r+1]
| n <- lst ]
intToList :: Int -> Integer -> [Int]
intToList b lst = go 0 $ toBase (b+1) lst
where
go 0 [] = []
go i (0:xs) = go (i+1) xs
go i (x:xs) = (i*b + x - 1) : go 0 xs</lang>
Using different bases we may enumerate lists.
<pre>*Main> intToList 2 <$> [1..20]
[[0],[1],[2],[0,0],[1,0],[3],[0,1],[1,1],[4],[0,2],[1,2],[2,0],[0,0,0],[1,0,0],[3,0],[0,1,0],[1,1,0],[5],[0,3],[1,3]]
*Main> intToList 3 <$> [1..20]
[[0],[1],[2],[3],[0,0],[1,0],[2,0],[4],[0,1],[1,1],[2,1],[5],[0,2],[1,2],[2,2],[6],[0,3],[1,3],[2,3],[3,0]]
*Main> intToList 10 <$> [1..20]
[[0],[1],[2],[3],[4],[5],[6],[7],[8],[9],[10],[0,0],[1,0],[2,0],[3,0],[4,0],[5,0],[6,0],[7,0],[8,0]]
*Main> listToInt 2 <$> permutations [1,2,3,4]
[2360,2370,2382,2406,2292,2288,5274,5190,5136,5922,5916,5160,4680,4646,4628,4950,4944,4638,2736,2702,2450,2844,2760,2454]</pre>
This mapping is a bijection:
<pre>*Main> (listToInt 3 . intToList 3 <$> [0..100]) == [0..100]
True</pre>
=={{header|J}}==
| |||