/*
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).