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

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