# An elegant codes on finding all permutations of a list **URL:** \ **Category:** General\ **Tags:** how-to, permutations\ **Created:** [June 1, 2023, 3:01pm UTC](https://swi-prolog.discourse.group/t/an-elegant-codes-on-finding-all-permutations-of-a-list/6598 "2023-06-01T15:01:43Z")\ **Posts on this page:** 1\ **Page:** 1
**Author:** ![kuniaki.mukai](https://avatars.discourse-cdn.com/v4/letter/k/c67d28/32.png) [@kuniaki.mukai](https://swi-prolog.discourse.group/u/kuniaki.mukai)\ **Post date:** [June 1, 2023, 3:01pm UTC](https://swi-prolog.discourse.group/t/an-elegant-codes-on-finding-all-permutations-of-a-list/6598/1 "2023-06-01T15:01:43Z")
**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** > > ```prolog > % ?- 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\ > > ``` > > ```prolog > % ?- 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. ```prolog % ?- 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). ```