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;

[]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:(

1. FOR FLEX[]ELEM try in # perm gen elemlist(combination #) DO (#,
   1. (PERMELEMLIST try)VOID: (

   printf((partner fmt,try))

1. 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