An elegant codes on finding all permutations of a list

General
,
1

EDIT 2023/06/03

I have compared robustness of the permutations/2 with 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 permutations/2. 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).

EDIT End

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:

  • append is 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).