Permutations with repetitions

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 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	${\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)$
Without replacement	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}$
With replacement	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 #

-*- 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 (#,
1. (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]

REXX

<lang rexx>/*REXX program generates all permutations with repeats of N objects.*/ parse arg things bunch inbetweenChars names

     /* inbetweenChars  (optional)   defaults to a  [null].            */
     /*          names  (optional)   defaults to digits (and letters). */

call permRsets things,bunch,inbetweenChars,names exit /*stick a fork in it, we're done.*/ /*──────────────────────────────────.PERMRSET subroutine────────────────*/ .permRset: procedure expose (list); parse arg ? if ?>y then do; _=@.1; do j=2 to y; _=_||between||@.j; end; say _; end

      else do q=1  for x              /*build permutation recursively. */
           @.?=$.q;      call .permRset ?+1
           end    /*q*/

return /*──────────────────────────────────PERMRSETS subroutine────────────────*/ permRsets: procedure; parse arg x,y,between,uSyms /*X things Y at a time*/ @.=; sep= /*X can't be > length(@0abcs). */ @abc = 'abcdefghijklmnopqrstuvwxyz'; @abcU=@abc; upper @abcU @abcS = @abcU || @abc; @0abcS=123456789 || @abcS

 do k=1  for x                        /*build a list of (perm) symbols.*/
 _=p(word(uSyms,k)  p(substr(@0abcS,k,1) k))   /*get|generate a symbol.*/
 if length(_)\==1  then sep='_'       /*if not 1st char, then use sep. */
 $.k=_                                /*append it to the symbol list.  */
 end   /*k*/

if between== then between=sep /*use the appropriate separator. */ list='$. @. between x y' call .permRset 1 return /*──────────────────────────────────P subroutine (Pick one)─────────────*/ p: return word(arg(1),1)</lang> output when using the input of: 3 2

11 12 13 21 22 23 31 32 33output when using the input of: 3 2 , bat fox cowbat,bat bat,fox bat,cow fox,bat fox,fox fox,cow cow,bat cow,fox cow,cow