Permutations with repetitions: Difference between revisions
m (fix typo) |
(→[[Permutations_with_repetitions#ALGOL 68]]: with test case candidates) |
||
Line 10: | Line 10: | ||
'''See Also:''' |
'''See Also:''' |
||
{{Template:Combinations and permutations}} |
{{Template:Combinations and permutations}} |
||
=={{header|ALGOL 68}}== |
|||
{{works with|ALGOL 68|Revision 1 - one minor extension to language used - PRAGMA READ, similar to C's #include directive.}} |
|||
{{works with|ALGOL 68G|Any - tested with release [http://sourceforge.net/projects/algol68/files/algol68g/algol68g-2.6 algol68g-2.6].}} |
|||
{{wont work with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release [http://sourceforge.net/projects/algol68/files/algol68toc/algol68toc-1.8.8d/algol68toc-1.8-8d.fc9.i386.rpm/download 1.8-8d] - due to extensive use of '''format'''[ted] ''transput''.}} |
|||
'''File: prelude_permutations_with_repetitions.a68'''<lang algol68># -*- coding: utf-8 -*- # |
|||
MODE PERMELEMLIST = FLEX[0]PERMELEM; |
|||
MODE PERMELEMLISTYIELD = PROC(PERMELEMLIST)VOID; |
|||
PROC perm gen elemlist = (FLEX[]PERMELEMLIST master, PERMELEMLISTYIELD yield)VOID:( |
|||
[LWB master:UPB master]INT counter; |
|||
[LWB master:UPB master]PERMELEM out; |
|||
FOR i FROM LWB counter TO UPB counter DO |
|||
INT c = counter[i] := LWB master[i]; |
|||
out[i] := master[i][c] |
|||
OD; |
|||
yield(out); |
|||
WHILE TRUE DO |
|||
INT next i := LWB counter; |
|||
counter[next i] +:= 1; |
|||
FOR i FROM LWB counter TO UPB counter WHILE counter[i]>UPB master[i] DO |
|||
INT c = counter[i] := LWB master[i]; |
|||
out[i] := master[i][c]; |
|||
next i := i + 1; |
|||
IF next i > UPB counter THEN done FI; |
|||
counter[next i] +:= 1 |
|||
OD; |
|||
INT c = counter[next i]; |
|||
out[next i] := master[next i][c]; |
|||
yield(out) |
|||
OD; |
|||
done: SKIP |
|||
); |
|||
SKIP</lang>'''File: test_permutations_with_repetitions.a68'''<lang algol68>#!/usr/bin/a68g --script # |
|||
# -*- coding: utf-8 -*- # |
|||
MODE PERMELEM = STRING; |
|||
PR READ "prelude_permutations_with_repetitions.a68" PR; |
|||
[]STRING wife list = ("Katie Holmes", "Nicole Kidman", "Mimi Rogers"); |
|||
[]STRING husband list = ("Keith Urban","Tom Cruise","Chris Ciaffa"); |
|||
FLEX[0]PERMELEMLIST combination := (husband list, wife list); |
|||
FORMAT partner fmt = $g" & "gl$; |
|||
test:( |
|||
# FOR FLEX[]ELEM try in # perm gen elemlist(combination #) DO (#, |
|||
## (PERMELEMLIST try)VOID: ( |
|||
printf((partner fmt,try)) |
|||
# OD #)) |
|||
)</lang>'''Output:''' |
|||
<pre> |
|||
Keith Urban & Katie Holmes |
|||
Tom Cruise & Katie Holmes |
|||
Chris Ciaffa & Katie Holmes |
|||
Keith Urban & Nicole Kidman |
|||
Tom Cruise & Nicole Kidman |
|||
Chris Ciaffa & Nicole Kidman |
|||
Keith Urban & Mimi Rogers |
|||
Tom Cruise & Mimi Rogers |
|||
Chris Ciaffa & Mimi Rogers |
|||
</pre> |
Revision as of 13:45, 26 April 2013
Generate a sequence of permutations of n elements drawn from choice of k values.
This sequence will have elements, unless the program decides to terminate early.
Do not store all the intermediate values ion the sequence, rather generate them as required, and pass the intermediate result to a deciding routine.
For example: When "cracking" a "combination" lock a sequence is required, but the sequence is terminated once a successful "combination" is found. This case is a good example of where it is not required to store all the intermediate permutations.
See Also:
The number of samples of size k from n objects.
With combinations and permutations generation tasks.
Order Unimportant Order Important Without replacement Task: Combinations Task: Permutations With replacement Task: Combinations with repetitions Task: Permutations with repetitions
ALGOL 68
File: prelude_permutations_with_repetitions.a68<lang algol68># -*- coding: utf-8 -*- #
MODE PERMELEMLIST = FLEX[0]PERMELEM; MODE PERMELEMLISTYIELD = PROC(PERMELEMLIST)VOID;
PROC perm gen elemlist = (FLEX[]PERMELEMLIST master, PERMELEMLISTYIELD yield)VOID:(
[LWB master:UPB master]INT counter; [LWB master:UPB master]PERMELEM out; FOR i FROM LWB counter TO UPB counter DO INT c = counter[i] := LWB master[i]; out[i] := master[i][c] OD; yield(out); WHILE TRUE DO INT next i := LWB counter; counter[next i] +:= 1; FOR i FROM LWB counter TO UPB counter WHILE counter[i]>UPB master[i] DO INT c = counter[i] := LWB master[i]; out[i] := master[i][c]; next i := i + 1; IF next i > UPB counter THEN done FI; counter[next i] +:= 1 OD; INT c = counter[next i]; out[next i] := master[next i][c]; yield(out) OD; done: SKIP
);
SKIP</lang>File: test_permutations_with_repetitions.a68<lang algol68>#!/usr/bin/a68g --script #
- -*- coding: utf-8 -*- #
MODE PERMELEM = STRING; PR READ "prelude_permutations_with_repetitions.a68" PR;
[]STRING wife list = ("Katie Holmes", "Nicole Kidman", "Mimi Rogers"); []STRING husband list = ("Keith Urban","Tom Cruise","Chris Ciaffa");
FLEX[0]PERMELEMLIST combination := (husband list, wife list);
FORMAT partner fmt = $g" & "gl$; test:(
- FOR FLEX[]ELEM try in # perm gen elemlist(combination #) DO (#,
- (PERMELEMLIST try)VOID: (
printf((partner fmt,try))
- OD #))
)</lang>Output:
Keith Urban & Katie Holmes Tom Cruise & Katie Holmes Chris Ciaffa & Katie Holmes Keith Urban & Nicole Kidman Tom Cruise & Nicole Kidman Chris Ciaffa & Nicole Kidman Keith Urban & Mimi Rogers Tom Cruise & Mimi Rogers Chris Ciaffa & Mimi Rogers