Permutations with repetitions

Permutations with repetitions is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Permutations with repetitions is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Generate a sequence of permutations of n elements drawn from choice of k values.

This sequence will have $n^{k}$ 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	${\binom {n}{k}}=^{n}\operatorname {C} _{k}={\frac {n(n-1)\ldots (n-k+1)}{k(k-1)\dots 1}}$	$^{n}\operatorname {P} _{k}=n\cdot (n-1)\cdot (n-2)\cdots (n-k+1)$
	Task: Combinations	Task: Permutations
With replacement	${\binom {n+k-1}{k}}=^{n+k-1}\operatorname {C} _{k}={(n+k-1)! \over (n-1)!k!}$	$n^{k}$
	Task: Combinations with repetitions	Task: Permutations with repetitions

ALGOL 68

Works with: ALGOL 68 version Revision 1 - one minor extension to language used - PRAGMA READ, similar to C's #include directive.

Works with: ALGOL 68G version Any - tested with release algol68g-2.6.

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 #

1. -*- coding: utf-8 -*- #

MODE PERMELEM = STRING; PR READ "prelude_permutations_with_repetitions.a68" PR;

INT husband = 1, wife = 2; PERMELEMLIST husband list = ("Keith Urban","Tom Cruise","Chris Ciaffa"); PERMELEMLIST wife list = ("Katie Holmes", "Nicole Kidman", "Mimi Rogers");

FLEX[0]PERMELEMLIST combination := (wife list, wife list);

FORMAT partner fmt = $g" & "g$; test:(

1. FOR PERMELEMELEM candidate in # perm gen elemlist(combination #) DO (#,
   1. (PERMELEMLIST candidate)VOID: (

   printf((partner fmt,candidate));
   IF candidate[husband] = "Keith Urban" AND candidate[wife]="Nicole Kidman" THEN
     print(" => Sunday + Faith") # children #
   FI;
   print(new line)

1. OD #))

)</lang>Output:

Katie Holmes & Katie Holmes
Nicole Kidman & Katie Holmes
Mimi Rogers & Katie Holmes
Katie Holmes & Nicole Kidman
Nicole Kidman & Nicole Kidman
Mimi Rogers & Nicole Kidman
Katie Holmes & Mimi Rogers
Nicole Kidman & Mimi Rogers
Mimi Rogers & Mimi Rogers

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]