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 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)$
	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 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:(

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

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

D

Translation of: Scala

<lang d>import std.array;

struct PermutationsWithRepetitions(T) {

   const T[] data;
   const int n;

   int opApply(int delegate(ref T[]) dg) {
       int result;
       T[] aux;

       if (n == 1) {
           foreach (el; data) {
               aux = [el];
               result = dg(aux);
               if (result) goto END;
           }
       } else {
           foreach (el; data) {
               foreach (p; PermutationsWithRepetitions(data, n - 1)) {
                   aux = el ~ p;
                   result = dg(aux);
                   if (result) goto END;
               }
           }
       }

       END:
       return result;
   }

}

auto permutationsWithRepetitions(T)(T[] data, in int n) pure nothrow in {

   assert(!data.empty && n > 0);

} body {

   return PermutationsWithRepetitions!T(data, n);

}

void main() {

   import std.stdio, std.array;
   [1, 2, 3].permutationsWithRepetitions(2).array.writeln;

}</lang>

Output:

[[1, 1], [1, 2], [1, 3], [2, 1], [2, 2], [2, 3], [3, 1], [3, 2], [3, 3]]

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]

Mathematica

<lang mathematica>Tuples[{1, 2, 3}, 2]</lang>

Output:

{{1, 1}, {1, 2}, {1, 3}, {2, 1}, {2, 2}, {2, 3}, {3, 1}, {3, 2}, {3, 3}}

Perl 6

Works with: rakudo version 2013-05-02

List operators such as X are naturally lazy in Perl 6. <lang perl6>my $k = <a b c>; my $n = 2;

.say for [X]($k xx $n).tree;</lang>

Output:

a a
a b
a c
b a
b b
b c
c a
c b
c c

REXX

version 1

<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
33

output when using the input of: 3 2 , bat fox cow

bat,bat
bat,fox
bat,cow
fox,bat
fox,fox
fox,cow
cow,bat
cow,fox
cow,cow

version 2 (using Interpret)

Note: this REXX version will cause Regina REXX to fail (crash) if the expression to be INTERPRETed is too large (byte-wise).
PC/REXX and Personal REXX also fail, but for a smaller expression.
Please specify limitations. One could add: If length(a)>implementation_dependent_limit Then
  Say 'too large for this Rexx version'
Also note that the output isn't the same as REXX version 1 when the 1st argument is two digits or more, i.e.:   11   2 <lang rexx>/* REXX ***************************************************************

• Arguments and output as in REXX version 1 (for the samples shown there)
• For other elements (such as 11 2), please specify a separator
• Translating 10, 11, etc. to A, B etc. is left to the reader
• 12.05.2013 Walter Pachl
• 12-05-2013 Walter Pachl take care of bunch<=0 and other oddities
  • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • /

Parse Arg things bunch sep names If datatype(things,'W') & datatype(bunch,'W') Then

 Nop

Else

 Call exit 'First two arguments must be integers >0'

If things= Then n=3; Else n=things If bunch= Then m=2; Else m=bunch If things<=0 Then Call exit 'specify a positive number of things' If bunch<=0 Then Call exit 'no permutations with' bunch 'elements!'

Select

 When sep= Then ss='
 When datatype(sep)='NUM' Then ss='copies(' ',sep)'
 Otherwise ss='sep'
 End

Do i=1 To n

 If names<> Then
   Parse Var names e.i names
 Else
   e.i=i
 End

a='p=0;'; Do i=1 To m; a=a||'Do p'i'=1 To n;'; End a=a||'ol=e.p1'

         Do i=2 To m; a=a||'||'ss'||e.p'i; End

a=a||'; say ol; p=p+1;'

         Do i=1 To m; a=a||'end;'; End

a=a||'Say' p 'permutations' /* Say a */ Interpret a</lang>

Scala

<lang scala>package permutationsRep

object PermutationsRepTest extends Application {

 /**
  * Calculates all permutations taking n elements of the input List, 
  * with repetitions. 
  * Precondition: input.length > 0 && n > 0
  */
 def permutationsWithRepetitions[T](input : List[T], n : Int) : List[List[T]] = {
   require(input.length > 0 && n > 0)
   n match {
     case 1 => for (el <- input) yield List(el)
     case _ => for (el <- input; perm <- permutationsWithRepetitions(input, n - 1)) yield el :: perm
   }
 }   
 println(permutationsWithRepetitions(List(1, 2, 3), 2))

}</lang>

Output:

List(List(1, 1), List(1, 2), List(1, 3), List(2, 1), List(2, 2), List(2, 3), List(3, 1), List(3, 2), List(3, 3))