Permutations: Difference between revisions
Content added Content deleted
Line 7,169: | Line 7,169: | ||
( ) ( 1 2 3 4 ) permute |
( ) ( 1 2 3 4 ) permute |
||
ps> sort print</lang> |
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}}== |
=={{header|PicoLisp}}== |