/* Euler #24 in Picat. """ 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? """ This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com See also my Picat page: http://www.hakank.org/picat/ */ import util. import cp. main => go. go => time(euler24). % about 0.9s euler24 => L = 0..9, C = 1, while (C < 1000000) L := next_permutation(L), C := C + 1 end, println([I.to_string() : I in L].flatten()). % Using CP: 5.7s euler24b => P = alldiff(10), writeln(P[1000000]). % Using perm/1: 8.6s euler24c => P = permutations(0..9).sort(), println(P[1000000]), nl. next_permutation(P) = Perm => Perm1 = P, N = Perm1.length, K = N - 1, while (Perm1[K] > Perm1[K+1], K >= 0) K := K - 1 end, if K > 0 then J = N, while (Perm1[K] > Perm1[J]) J := J - 1 end, % [Perm1[K],Perm1[J]] = [Perm1[J], Perm1[K]], % don't work Tmp := Perm1[K], Perm1[K] := Perm1[J], Perm1[J] := Tmp, R = N, S = K + 1, while (R > S) % [Perm1[R],Perm1[S]] = [Perm1[S],Perm1[R]], % don't work Tmp := Perm1[R], Perm1[R] := Perm1[S], Perm1[S] := Tmp, R := R - 1, S := S + 1 end end, Perm = Perm1. % CP version. % solve_all/1 happens to yield all % permutations is correct order. alldiff(N) = Perms => P = new_list(N), P :: 0..N-1, all_different(P), Perms = solve_all(P).