blob: 5db0aaab733fbbe2cc158684e8cfa4c0d359af69 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
-- Lexicographic permutations
--
-- Problem 24
-- A permutation is an ordered arrangement of objects. For example, 3124 is one possible
-- permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically
-- or alphabetically, we call it lexicographic order. The lexicographic permutations of
-- 0, 1 and 2 are:
--
-- 012 021 102 120 201 210
--
-- What is the millionth lexicographic permutation of the digits
-- 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?
import Data.Char(chr,ord)
main = print (foldr (\x acc -> chr (ord '0' + x) : acc) "" ((permutations' [0..9]) !! 999999))
permutations' :: [Int] -> [[Int]]
permutations' [x] = [[x]]
permutations' xs = concat [[x : p | p <- permutations' (filter (x/=) xs)] | x <- xs]
|
