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.List
digit="0123456789"
lexPerm =[[a,b,c,d,e,f,g,h,i,j]|a<-digit,b<-digit[a],c<-digit[a,b],
d<-digit [a,b,c],e<-digit[a,b,c,d],f<-digit[a,b,c,d,e],
g<-digit[a,b,c,d,e,f],h<-digit[a,b,c,d,e,f,g],
i<-digit[a,b,c,d,e,f,g,h],j<-digit[a,b,c,d,e,f,g,h,i]]
main = print$lexPerm!!999999

同じことを再帰を用いて

import Data.List
perm [] = [[]]
perm l = [a:b|a<-l,b<-perm$delete a l]
main =print $ perm "0123456789"!! 999999

こっちのほうが断然いいな。

More Reading
Newer// Problem 16
Older// Problem 10