Permutations with repetitions
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 of the sequence, rather generate them as required, and pass the intermediate result to a deciding routine for combinations selection and/or early generator termination.
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;
INT lead actor = 1, co star = 2; PERMELEMLIST actors list = ("Chris Ciaffa", "Keith Urban","Tom Cruise",
"Katie Holmes","Mimi Rogers","Nicole Kidman");
FLEX[0]PERMELEMLIST combination := (actors list, actors list, actors list, actors list);
FORMAT partner fmt = $g"; "$; test:(
- FOR PERMELEMELEM candidate in # perm gen elemlist(combination #) DO (#,
- (PERMELEMLIST candidate)VOID: (
printf((partner fmt,candidate)); IF candidate[lead actor] = "Keith Urban" AND candidate[co star]="Nicole Kidman" OR candidate[co star] = "Keith Urban" AND candidate[lead actor]="Nicole Kidman" THEN print((" => Sunday + Faith as extras", new line)); # children # done FI; print(new line)
- OD #));
done: SKIP
)</lang>Output:
Chris Ciaffa; Chris Ciaffa; Chris Ciaffa; Chris Ciaffa; Keith Urban; Chris Ciaffa; Chris Ciaffa; Chris Ciaffa; Tom Cruise; Chris Ciaffa; Chris Ciaffa; Chris Ciaffa; Katie Holmes; Chris Ciaffa; Chris Ciaffa; Chris Ciaffa; Mimi Rogers; Chris Ciaffa; Chris Ciaffa; Chris Ciaffa; Nicole Kidman; Chris Ciaffa; Chris Ciaffa; Chris Ciaffa; Chris Ciaffa; Keith Urban; Chris Ciaffa; Chris Ciaffa; Keith Urban; Keith Urban; Chris Ciaffa; Chris Ciaffa; Tom Cruise; Keith Urban; Chris Ciaffa; Chris Ciaffa; Katie Holmes; Keith Urban; Chris Ciaffa; Chris Ciaffa; Mimi Rogers; Keith Urban; Chris Ciaffa; Chris Ciaffa; Nicole Kidman; Keith Urban; Chris Ciaffa; Chris Ciaffa; => Sunday + Faith as extras
Haskell
<lang haskell>import Control.Monad (replicateM)
main = mapM_ print (replicateM 2 [1,2,3])</lang>
- Output:
[1,1] [1,2] [1,3] [2,1] [2,2] [2,3] [3,1] [3,2] [3,3]