Permutations: Difference between revisions
ada version
m (→{{header|Tcl}}: use better template) |
(ada version) |
||
Line 4:
(c.f. [[Find the missing permutation]] )
=={{header|Ada}}==
<lang ada>-- perm.adb
-- print all permutations of 1 .. n
-- where n is given as a command line argument
-- to compile with gnat : gnatmake perm.adb
-- to call : perm n
with ada.text_io, ada.command_line;
procedure perm is
use ada.text_io, ada.command_line;
n : integer;
begin
if argument_count /= 1
then
put_line (command_name & " n (with n >= 1)");
else
n := integer'value (argument (1));
end if;
declare
subtype element is integer range 1..n;
type permutation is array (element'range) of element;
p : permutation;
is_last : boolean := false;
-- compute next permutation in lexicographic order
-- iterative algorithm :
-- find longest tail-decreasing sequence in p
-- the elements from this tail cannot be permuted to get a new permutation, so
-- reverse this tail, to start from an increaing sequence, and
-- exchange the element x preceding the tail, with the minimum value in the tail,
-- that is also greater than x
procedure next is
i, j, k, t : element;
begin
-- find longest tail decreasing sequence
-- after the loop, this sequence is i+1 .. n,
-- and the ith element will be exchanged later
-- with some element of the tail
is_last := true;
i := n - 1;
loop
if p (i) < p (i+1)
then
is_last := false;
exit;
end if;
if i = 1 then
exit;
end if;
i := i - 1;
end loop;
-- if all the elements of the permutation are in
-- decreasing order, this is the last one
if is_last then
return;
end if;
-- sort the tail, i.e. reverse it, since it is in decreasing order
j := i + 1;
k := n;
while j < k loop
t := p (j);
p (j) := p (k);
p (k) := t;
j := j + 1;
k := k - 1;
end loop;
-- find lowest element in the tail greater than the ith element
j := n;
while p (j) > p (i) loop
j := j - 1;
end loop;
j := j + 1;
-- exchange them
-- this will give the next permutation in lexicographic order,
-- since every element from ith to the last is minimum
t := p (i);
p (i) := p (j);
p (j) := t;
end next;
procedure print is
begin
for i in element'range loop
put (integer'image (p (i)));
end loop;
new_line;
end print;
begin
-- initialize the permutation
for i in element'range loop
p (i) := i;
end loop;
print;
loop
next;
if is_last
then
exit;
else
print;
end if;
end loop;
end;
end perm;</lang>
=={{header|C}}==
Iterative method. Given a permutation, find the next in lexicographic order. Iterate until the last one.
| |||