Permutations with repetitions: Difference between revisions
Walterpachl (talk | contribs) (→version 2 (using Interpret): address limitations) |
Walterpachl (talk | contribs) (→version 2 (using Interpret): more corrections) |
||
Line 238: | Line 238: | ||
<br> Say 'too large for this Rexx version' |
<br> Say 'too large for this Rexx version' |
||
<br>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''' |
<br>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''' |
||
<br>Also note that if ''bunch'' is 0 (zero), a '''null''' or some such indicator should be shown. |
|||
<lang rexx>/* REXX *************************************************************** |
<lang rexx>/* REXX *************************************************************** |
||
* Arguments and output as in REXX version 1 (for the samples shown there) |
* Arguments and output as in REXX version 1 (for the samples shown there) |
||
Line 244: | Line 243: | ||
* Translating 10, 11, etc. to A, B etc. is left to the reader |
* Translating 10, 11, etc. to A, B etc. is left to the reader |
||
* 12.05.2013 Walter Pachl |
* 12.05.2013 Walter Pachl |
||
* 12-05-2013 Walter Pachl take care of bunch<=0 and other oddities |
|||
**********************************************************************/ |
**********************************************************************/ |
||
Parse Arg things bunch sep names |
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 things='' Then n=3; Else n=things |
||
If bunch='' Then m=2; Else m=bunch |
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 |
Select |
||
When sep='' Then ss='''''' |
When sep='' Then ss='''''' |
||
Line 267: | Line 274: | ||
/* Say a */ |
/* Say a */ |
||
Interpret a</lang> |
Interpret a</lang> |
||
Exit |
|||
exit: Say arg(1) |
|||
=={{header|Scala}}== |
=={{header|Scala}}== |
Revision as of 20:39, 12 May 2013
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
D
<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
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> Exit exit: Say arg(1)
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))