# A small extension to ZDD for sets and lists to coexist enumerates permutations of a list of length 13

By making small extension to the ZDD library in pack pac-1.6.8, I have tested to enumerate all permutations of a list of length 13, which took around 5 seconds. The purpose of this experiment is to see if it is really easy to extend ZDD so that families of sets (ZDD) and familiies of lists which is unordered can coexist. Although this might be a folklore, I have noticed this possibility only recently while I observed that only one basic operation (`zdd_insert`) in the libary is aware of the given order.
The others do not touch the given order, which is a little bit striking for me. Also this experiment shows that structure sharing for zdd also works for unordered lists as well. I am not sure for now whether this coexistence of lists and sets is a direction to go. Anyway I need to take some time for experience further.

``````% ?- factorial(13, F).
%@ F = 6227020800 .

% ?- N = 13, use_state(S), numlist(1, N, Ns), time(unord_permutations(Ns, X, S)), card(X, C, S).
%@ % 15,526,827 inferences, 4.863 CPU in 8.116 seconds (60% CPU, 3192892 Lips)
%@ N = 13,
%@ S = ..,
%@ Ns = [1, 2, 3, 4, 5, 6, 7, 8, 9|...],
%@ X = 212960,
%@ C = 6227020800.
``````
``````unord_permutations([], 1, _).
unord_permutations([A|As], P, S):-
unord_permutations(As, Q, S),
insert_elem(A, Q, P, S).
%
insert_elem(_, 0, 0, _):-!.
insert_elem(A, 1, X, S):-!, zdd_singleton(A, X, S).
insert_elem(A, X, Y, S):- memo(insert_elem(A, X)-Y, S),
(	nonvar(Y) -> true		% , write(.)  % Many hits.
;	cofact(X, t(B, L, R), S),
insert_elem(A, L, L0, S),
zdd_unord_append([A, B], R, R1, S),
insert_elem(A, R, R2, S),
zdd_cons(R3, B, R2, S),
zdd_join_list([L0,  R1, R3], Y, S)
).
``````

EDIT [2022/10/25]

Here is a comparison with the ordinal prolog codes enumerating permutations. The difference is clear: unordered ZDD enumerate for 17 in about 30 seconds, the usual coding for 11 in about 60 seconds. BTW, I was surprised rather at seeing the ordianal coding managed to enumerate the permutations of a list of length 11. Very fast, I think.

``````% ?- N = 17, use_state(S), numlist(1, N, Ns), time(unord_permutations(Ns, X, S)), card(X, C, S).
%@ % 329,943,372 inferences, 28.740 CPU in 32.671 seconds (88% CPU, 11480190 Lips)
%@ N = 17,
%@ S = ..,
%@ Ns = [1, 2, 3, 4, 5, 6, 7, 8, 9|...],
%@ X = 4718514,
%@ C = 355687428096000.
``````

Usual codes in prolog.

``````% ?- permutations([a,b,c],X).
% X = [[a, b, c], [b, a, c], [b, c, a], [a, c, b], [c, a, b], [c, b, a]]

% ?- N = 11, numlist(1, N, Ns), call_with_time_limit(100, time(math:permutations(Ns, X))), length(X, Len).
%@ % 570,948,961 inferences, 54.743 CPU in 74.897 seconds (73% CPU, 10429706 Lips)
%@ N = 11,
%@ Ns = [1, 2, 3, 4, 5, 6, 7, 8, 9|...],
%@ X = [[1, 2, 3, 4, 5, 6, 7, 8|...], [2, 1, 3, 4, 5, 6, 7|...], [2, 3, 1, 4, 5, 6|...], [2, 3, 4, 1, 5|...], [2, 3, 4, 5|...], [2, 3, 4|...], [2, 3|...], [2|...], [...|...]|...],
%@ Len = 39916800.

permutations([], [[]]).
permutations([X|Xs], Ps):- permutations(Xs, Qs),
permutations(X, Qs, Ps).

permutations(_, [], []).
permutations(X, [P|Ps], L):- insert_list(X, P, P0),
permutations(X, Ps, Qs),
append(P0, Qs, L).

% ?- insert_list(a, [1,2], X).
% X = [[a, 1, 2], [1, a, 2], [1, 2, a]]
insert_list(X, [], [[X]]).
insert_list(X, [A|As], [[X,A|As]|L]):-insert_list(X, As, L0),
maplist(cons(A), L0, L).
%
cons(X, Y, [X|Y]).
``````