I have compared robustness of the
all_perm/2. The all_perm/2` works on my experimetal ZDD library in Pack/pac. ( Note that the ZDD library can be used with some care as if the atoms were not ordered.)
According to the experiment below,
all_perm could be at leaset about
12 x 13 x 14 x 15
times more robust than the
permutions/2 does not care about any structure sharing but only stylish aspect of programming. On the other hand,
all_perm works on the systematic structure sharing. My quick words for impression after this experiment, ZDD version seemed more easy to write than that on the standard list processing. I am not sure why. To find all the permutations might be an exceptional case.
Statistics of experiment
% ?- time((N = 11, numlist(1, N, Ns), permutations(Ns, Ps), length(Ps, Len))), % writeln(pass(N)), fail; writeln("\nDone.\n"). %@ % 309,470,824 inferences, 14.952 CPU in 17.814 seconds (84% CPU, 20697790 Lips) %@ pass(11) %@ %@ Done. % ?- call_with_time_limit(120, time((N = 12, numlist(1, N, Ns), permutations(Ns, Ps), length(Ps, Len)))), % writeln(pass(N)), fail; writeln("\nDone.\n"). %@ % 878,420,042 inferences, 85.383 CPU in 268.075 seconds (32% CPU, 10288036 Lips) %@ ERROR: Unhandled exception: Time limit exceeded\
% ?- N=15, time((numlist(1, N, Ns), (zdd all_perm(Ns, X), card(X, C)))). %@ % 84,073,484 inferences, 47.282 CPU in 47.647 seconds (99% CPU, 1778120 Lips) %@ N = 15, %@ X = 1105921, %@ C = 1,307,674,368,000. all_perm(D, P, S):- zdd_sort(D, D0, S), findall_perm(D0, P, S). % findall_perm(, 1, _):-!. findall_perm(D, X, S):- memo(perm(D)-X, S), ( nonvar(X) -> true % , write(.) % many hits. ; findall(I-D0, select(I, D, D0), U), join_perm_for_selection(U, 0, X, S)). % join_perm_for_selection(, X, X, _). join_perm_for_selection([I-D|U], X, Y, S):- findall_perm(D, X0, S), zdd_cons(X1, I, X0, S), zdd_join(X1, X, X2, S), join_perm_for_selection(U, X2, Y, S).
How do you write codes on finding all permutations of a list ? So far I had several chances to write codes for that, but this is my first time to write successfully an “elegant” one from my point of view:
appendis not used.
- ! (cut) is not used.
- right recursive form (Tail Rcursion form ?).
However I have to use reverse/3 with stack. I would like to see more elegant one which does not use the reverse.
% ?- permutations([a,b,c],X), length(X, Len). % ?- between(1, 11, N), numlist(1, N, Ns), permutations(Ns, Ps), % length(Ps, Len), % factorial(N, Len), writeln(pass(N)), fail; writeln("\nDone.\n"). reverse(, X, X). reverse([A|As], X, Y):- reverse(As, [A|X], Y). permutations(As, Ps):- permutations(As, [], Ps). % permutations(, Ps, Ps). permutations([X|Xs], Ps, Qs):- permutations(Ps, X, Rs, ), permutations(Xs, Rs, Qs). % permutations(, _, Ps, Ps). permutations([P|Ps], X, Qs, Rs):- permutations(P, X, , Qs, Us), permutations(Ps, X, Us, Rs). % permutations(, X, Bs, [U|Ps], Ps):- reverse(Bs, [X], U). permutations([A|As], X, Bs, [U|Ps], Qs):- reverse(Bs, [X, A|As], U), permutations(As, X, [A|Bs], Ps, Qs).