Anonymous user
Permutations: Difference between revisions
m
<lang> needs a language
(+ second D entry (lazy)) |
m (<lang> needs a language) |
||
Line 1:
{{task|Discrete math}}
Write a program which generates the all [[wp:Permutation|permutations]] of '''n''' different objects. (Practically numerals!)
;C.f.
* [[Find the missing permutation]]
Line 8 ⟶ 6:
=={{header|ABAP}}==
<lang ABAP>data: lv_flag type c,
lv_number type i,
lt_numbers type table of i.
Line 109 ⟶ 106:
modify iv_set index lv_len from lv_temp.
endform.</lang>
{{out}}
<pre>
1, 3, 2
2, 1, 3
Line 234 ⟶ 231:
end perm;</lang>
=={{header|ALGOL 68}}==
{{works with|ALGOL 68|Revision 1 - one minor extension to language used - PRAGMA READ, like C's #include directive.}}
Line 323 ⟶ 321:
printf(($f(values fmt)l$, PERM test case))
)</lang>
{{out}}
<pre>
Number of permutations: +24
Line 402 ⟶ 400:
o := A_LoopField o
return o
}</lang>
{{out}}
<pre style="height:40ex;overflow:scroll">Hello
Helol
Line 465 ⟶ 462:
ollHe
olleH</pre>
=={{header|BBC BASIC}}==
The procedure PROC_NextPermutation() will give the next lexicographic permutation of an integer array.
<lang BBC BASIC> DEF PROC_NextPermutation(A%())
LOCAL first, last, elementcount, pos
elementcount = DIM(A%(),1)
Line 495 ⟶ 491:
last -= 1
ENDWHILE
ENDPROC</lang>
=={{header|C}}==
Line 602 ⟶ 597:
=={{header|C++}}==
The C++ standard library provides for this in the form of <code>std::next_permutation</code> and <code>std::prev_permutation</code>.
<lang cpp>#include <algorithm>
#include <string>
Line 644 ⟶ 638:
return 0;
}</lang>
{{out}}
<pre>
Hello
Line 721 ⟶ 715:
=={{header|Clojure}}==
In an REPL:
<lang clojure>user=> (require 'clojure.contrib.combinatorics)
nil
Line 746 ⟶ 739:
# Flatten the array before returning it.
[].concat permutations...</lang>
This implementation utilises the fact that the permutations of an array could be defined recursively, with the fixed point being the permutations of an empty array.
{{out|Usage}}
<lang coffeescript>coffee> console.log (permute "123").join "\n"
1,2,3
Line 767 ⟶ 758:
'(()))) ; else
(print (permute '(A B Z)
{{out}}
<pre>((A B Z) (A Z B) (B A Z) (B Z A) (Z A B) (Z B A))</pre>
Lexicographic next permutation:
<lang lisp>(defun next-perm (vec cmp) ; modify vector
(declare (type (simple-array * (*)) vec))
(macrolet ((el (i) `(aref vec ,i))
Line 788 ⟶ 779:
;;; test code
(loop for a = "1234" then (next-perm a #'char<) while a do
(write-line a))</lang>
=={{header|D}}==
Line 814 ⟶ 804:
writeln(p);
}</lang>
{{out}}
<pre>[1, 2, 3]
[1, 3, 2]
Line 941 ⟶ 931:
Readln;
end.</lang>
{{out}}
<pre>
4123 4213 4312 4321 4132 4231 3421
Line 955 ⟶ 945:
permute([]) -> [[]];
permute(L) -> [[X|Y] || X<-L, Y<-permute(L--[X])].</lang>
Y-combinator (for shell):
<lang Erlang>F = fun(L) -> G = fun(_, []) -> [[]]; (F, L) -> [[X|Y] || X<-L, Y<-F(F, L--[X])] end, G(G, L) end.</lang>
More efficient zipper implementation:
<lang Erlang>-module(permute).
Line 979 ⟶ 966:
prepend(_, [], T, R) -> zipper(T, R); % continue in zipper
prepend(X, [H|T], ZT, ZR) -> [[X|H] | prepend(X, T, ZT, ZR)].</lang>
Demonstration (escript):
<lang Erlang>main(_) -> io:fwrite("~p~n", [permute:permute([1,2,3])]).</lang>
{{out}}
<pre>[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]</pre>
Line 1,040 ⟶ 1,022:
puts(1, s & '\t')
end while</lang>
{{out}}
<pre>abcd abdc acbd acdb adbc adcb bacd badc bcad bcda
bdac bdca cabd cadb cbad cbda cdab cdba dabc dacb
Line 1,083 ⟶ 1,064:
end program permutations</lang>
{{out}}
<
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1</
Here is an alternate, iterative version in Fortran 77.
{{trans|Ada}}
<lang fortran> program nptest
integer n,i,a
Line 1,149 ⟶ 1,130:
# All permutations of 1..4
PermutationsList([1..4]);</lang>
=={{header|Go}}==
<lang go>package main
Line 1,202 ⟶ 1,184:
rc(len(s))
}</lang>
{{out}}
<pre>[1 2 3]
[1 3 2]
Line 1,213 ⟶ 1,195:
Solution:
<lang groovy>def makePermutations = { l -> l.permutations() }</lang>
Test:
<lang groovy>def list = ['Crosby', 'Stills', 'Nash', 'Young']
Line 1,219 ⟶ 1,200:
assert permutations.size() == (1..<(list.size()+1)).inject(1) { prod, i -> prod*i }
permutations.each { println it }</lang>
{{out}}
<pre style="height:30ex;overflow:scroll;">[Young, Crosby, Stills, Nash]
[Crosby, Stills, Young, Nash]
Line 1,251 ⟶ 1,231:
main = mapM_ print (permutations [1,2,3])</lang>
<lang haskell>import Data.List (delete)
permutations [] = [[]]
permutations xs = [ x:ys | x <- xs, ys <- permutations (delete x xs)]</lang>
=={{header|Icon}} and {{header|Unicon}}==
Line 1,267 ⟶ 1,245:
suspend [(A[1]<->A[i := 1 to *A])] ||| permute(A[2:0])
end</lang>
{{out}}
<pre>->permute Aardvarks eat ants
Aardvarks eat ants
Line 1,278 ⟶ 1,256:
=={{header|J}}==
<lang j>perms=: A.&i.~ !</lang>
{{out|Example use}}
<lang j> perms 2
0 1
Line 1,379 ⟶ 1,354:
} // class</lang>
{{out}}
<pre>
1 2 3
Line 1,390 ⟶ 1,363:
3 2 1
</pre>
'''optimized'''
Following needs: [[User:Margusmartsepp/Contributions/Java/Utils.java|Utils.java]]
<lang java>public class Permutations {
public static void main(String[] args) {
System.out.println(Utils.Permutations(Utils.mRange(1, 3)));
}
}</lang>
{{out}}
<pre>[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]</pre>
Line 1,470 ⟶ 1,438:
:- end_object.</lang>
{{out|Usage example
<lang logtalk>| ?- forall(list::permutation([1, 2, 3], Permutation), (write(Permutation), nl)).
Line 1,480 ⟶ 1,448:
[3,2,1]
yes</lang>
=={{header|Mathematica}}==
<lang Mathematica>Permutations[{1,2,3,4}]</lang>
{{out}}
<pre>{{1, 2, 3, 4}, {1, 2, 4, 3}, {1, 3, 2, 4}, {1, 3, 4, 2}, {1, 4, 2, 3}, {1, 4, 3, 2}, {2, 1, 3, 4}, {2, 1, 4, 3}, {2, 3, 1, 4}, {2, 3,
4, 1}, {2, 4, 1, 3}, {2, 4, 3, 1}, {3, 1, 2, 4}, {3, 1, 4, 2}, {3, 2, 1, 4}, {3, 2, 4, 1}, {3, 4, 1, 2}, {3, 4, 2, 1}, {4, 1, 2,
Line 1,682 ⟶ 1,648:
}
@input = (a,2,c,4);
&permutation('',@input);</lang>
{{out}}
<pre>
a2c4
Line 1,731 ⟶ 1,695:
.say for [<a b c>], &next_perm ...^ !*;</lang>
{{out}}
a c b
b a c
Line 1,744 ⟶ 1,708:
(permute (1 2 3))</lang>
{{out}}
<pre>-> ((1 2 3) (1 3 2) (2 1 3) (2 3 1) (3 1 2) (3 2 1))</pre>
Line 1,784 ⟶ 1,748:
all_different(L),
label(L).</lang>
{{out}}
<lang Prolog>?- permut_clpfd(L, 3), writeln(L), fail.
[1,2,3]
Line 1,793 ⟶ 1,757:
[3,2,1]
false.
</lang>
A declarative way of fetching permutations:
<lang Prolog>% permut_Prolog(P, L)
% P is a permutation of L
Line 1,801 ⟶ 1,766:
select(H, NL, NL1),
permut_Prolog(T, NL1).</lang>
{{out}}
<lang Prolog> ?- permut_Prolog(P, [ab, cd, ef]), writeln(P), fail.
[ab,cd,ef]
Line 1,809 ⟶ 1,774:
[ef,ab,cd]
[ef,cd,ab]
false.</lang>
=={{header|PureBasic}}==
Line 1,873 ⟶ 1,837:
CloseConsole()
EndIf</lang>
{{out}}
<pre>1, 2, 3
1, 3, 2
Line 1,885 ⟶ 1,849:
<lang python>import itertools
for values in itertools.permutations([1,2,3]):
print (values)</lang>
{{out}}
<pre>
(1, 2, 3)
Line 1,919 ⟶ 1,881:
(insert P N H))
(seq 0 (length P))))
(permute T))))</lang>
=={{header|R}}==
Line 1,973 ⟶ 1,934:
=={{header|REXX}}==
<lang rexx>/*REXX program to find the missing permutation. */
Line 2,030 ⟶ 1,990:
/*────────────────────────────────P subroutine (Pick one)───────────────*/
p: return word(arg(1),1)</lang>
{{out|Output for input <tt>3 3</tt>}}
<pre>
123
132
Line 2,043 ⟶ 2,000:
321
</pre>
{{out|Output
<pre style="height:15ex;overflow:scroll">
A---B---C---D
Line 2,103 ⟶ 2,058:
=={{header|Ruby}}==
{{works with|Ruby|1.8.7+}}
<lang ruby>p [1,2,3].permutation.to_a</lang>
{{out}}
<pre>
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
</pre>
However, this method will produce indistinct permutations if the array has indistinct elements. If you need to find all the permutations of an array of which many elements are the same, the method below will be more efficient.
<lang ruby>class Array
# Yields distinct permutations of _self_ to the block.
Line 2,198 ⟶ 2,149:
=={{header|Scala}}==
There is a built-in function that works on any sequential collection. It could be used as follows given a List of symbols:
<lang scala>List('a, 'b, 'c).permutations foreach println</lang>
{{out}}
<pre>List('a, 'b, 'c)
List('a, 'c, 'b)
Line 2,209 ⟶ 2,160:
=={{header|Scheme}}==
{{trans|Erlang}}
<lang scheme>(define (insert l n e)
(if (= 0 n)
(cons e l)
Line 2,229 ⟶ 2,178:
(insert p n (car l)))
(seq 0 (length p))))
(permute (cdr l))))))</lang>
{{trans|OCaml}}
<lang scheme>; translation of ocaml : mostly iterative, with auxiliary recursive functions for some loops
Line 2,294 ⟶ 2,241:
; 2 0 1
; 2 1 0</lang>
Completely recursive on lists:
<lang lisp>(define (perm s)
Line 2,346 ⟶ 2,292:
end for;
end func;</lang>
{{out}}
<pre>
1 2 3
Line 2,386 ⟶ 2,331:
=={{header|Ursala}}==
In practice there's no need to write this because it's in the standard library.
<lang Ursala>#import std
Line 2,402 ⟶ 2,345:
test = permutations <1,2,3></lang>
{{out}}
<pre><
<1,2,3>,
Line 2,412 ⟶ 2,355:
=={{header|VBA}}==
{{trans|Pascal}}
<lang VBA>Public Sub Permute(n As Integer, Optional printem As Boolean = True)
'generate, count and print (if printem is not false) all permutations of first n integers
Line 2,478 ⟶ 2,419:
Debug.Print "Number of permutations: "; count
End Sub</lang>
{{out|Sample dialogue}}
<pre>
permute 1
| |||