Permutations: Difference between revisions
→{{header|Picat}}
Line 7,169:
( ) ( 1 2 3 4 ) permute
ps> sort print</lang>
=={{header|Picat}}==
Picat has built-in support for permutations:
* <code>permutation(L)</code>: Generates all permutations for a list L.
* <code>permutation(L,P)</code>: Generates (via backtracking) all permutations for a list L.
===Recursion===
Use <code>findall/2</code> to find all permutations. See example below.
<lang Picat>permutation_rec1([X|Y],Z) :-
permutation_rec1(Y,W),
select(X,Z,W).
permutation_rec1([],[]).
permutation_rec2([], []).
permutation_rec2([X], [X]) :-!.
permutation_rec2([T|H], X) :-
permutation_rec2(H, H1),
append(L1, L2, H1),
append(L1, [T], X1),
append(X1, L2, X).</lang>
===Constraint modelling===
Constraint modelling only handles integers, and here generates all permutations of a list 1..N for a given N.
<code>permutation_cp_list(L)</code> permutes a list via <code>permutation_cp2/1</code>.
<lang Picat>import cp.
% Returns all permutations
permutation_cp1(N) = solve_all(X) =>
X = new_list(N),
X :: 1..N,
all_different(X).
% Find next permutation on backtracking
permutation_cp2(N,X) =>
X = new_list(N),
X :: 1..N,
all_different(X),
solve(X).
% Use the cp approach on a list L.
permutation_cp_list(L) = Perms =>
Perms = [ [L[I] : I in P] : P in permutation_cp1(L.len)].</lang>
===Tests===
Here is a test of the different approaches, including the two built-ins.
<lang Picat>import util, cp.
main =>
N = 3,
println(permutations=permutations(1..N)), % built in
println(permutation=findall(P,permutation([a,b,c],P))), % built-in
println(permutation_rec1=findall(P,permutation_rec1(1..N,P))),
println(permutation_rec2=findall(P,permutation_rec2(1..N,P))),
println(permutation_cp1=permutation_cp1(N)),
println(permutation_cp2=findall(P,permutation_cp2(N,P))),
println(permutation_cp_list=permutation_cp_list("abc")).</lang>
{{out}}
<pre>permutations = [[1,2,3],[2,1,3],[2,3,1],[1,3,2],[3,1,2],[3,2,1]]
permutation = [abc,acb,bac,bca,cab,cba]
permutation_rec1 = [[1,2,3],[2,1,3],[2,3,1],[1,3,2],[3,1,2],[3,2,1]]
permutation_rec2 = [[1,2,3],[2,1,3],[2,3,1],[1,3,2],[3,1,2],[3,2,1]]
permutation_cp1 = [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
permutation_cp2 = [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
permutation_cp_list = [abc,acb,bac,bca,cab,cba]</pre>
=={{header|PicoLisp}}==
| |||