Combinations with repetitions: Difference between revisions

Content added Content deleted
(Updated D code)
Line 189: Line 189:
=={{header|D}}==
=={{header|D}}==
Using [http://www-graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation lexicographic next bit permutation] to generate combinations with repetitions.
Using [http://www-graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation lexicographic next bit permutation] to generate combinations with repetitions.
<lang d>import std.stdio, std.range ;
<lang d>import std.stdio, std.range;


struct CombRep {
/*immutable*/ const struct CombRep {
immutable uint nt, nc ;
immutable uint nt, nc;
private ulong[] combVal;
private /*immutable*/ ulong[] combVal;

this(uint numType, uint numChoice) {
this(in uint numType, in uint numChoice) pure nothrow {
assert(0 < numType && numType + numChoice <= 64,
assert(0 < numType && numType + numChoice <= 64,
"valid only for nt + nc <= 64 (ulong bit size)") ;
"valid only for nt + nc <= 64 (ulong bit size)");
nt = numType ;
nt = numType;
nc = numChoice ;
nc = numChoice;
if(nc == 0) return ;
if (nc == 0)
auto v = (1UL << (nt - 1)) - 1 ;
return;
auto v = (1UL << (nt - 1)) - 1;

// init to smallest number that has nt-1 bit set
// init to smallest number that has nt-1 bit set
// a set bit is metaphored as a _type_ seperator
// a set bit is metaphored as a _type_ seperator
immutable limit = v << nc ;
immutable limit = v << nc;

// limit is the largest nt-1 bit set number that has nc zero-bit
// a zero-bit means a _choice_ between _type_ seperators
// limit is the largest nt-1 bit set number that has nc
// zero-bit a zero-bit means a _choice_ between _type_
⚫
while(v <= limit) {
combVal ~= v ;
// seperators
if(v == 0) break ;
while (v <= limit) {
auto t = (v | (v - 1)) + 1 ; // get next nt-1 bit number
combVal ~= v;
v = t | ((((t & -t) / (v & -v)) >> 1) - 1) ;
if (v == 0)
break;
// get next nt-1 bit number
immutable t = (v | (v - 1)) + 1;
v = t | ((((t & -t) / (v & -v)) >> 1) - 1);
}
}
}
}

⚫
uint length() @property { return combVal.length ; }
uint[] opIndex(uint idx) { return val2set(combVal[idx]) ; }
uint length() @property const pure nothrow {
⚫
return combVal.length;
}

uint[] opIndex(in uint idx) const pure nothrow {
return val2set(combVal[idx]);
}

int opApply(int delegate(ref uint[]) dg) {
int opApply(int delegate(ref uint[]) dg) {
foreach(v;combVal) {
foreach (v; combVal) {
auto set = val2set(v) ;
auto set = val2set(v);
if(dg(set))
if (dg(set))
break ;
break;
}
}
return 1 ;
return 1;
}
}

private uint[] val2set(ulong v) pure {
private uint[] val2set(in ulong v) const pure nothrow {
// convert bit pattern to selection set
// convert bit pattern to selection set
uint typeIdx = 0, bitLimit = nt + nc - 1 ;
immutable uint bitLimit = nt + nc - 1;
uint[] set ;
uint typeIdx = 0;
foreach(bitNum; 0..bitLimit)
uint[] set;
if(v & (1 << bitLimit - bitNum - 1))
foreach (bitNum; 0 .. bitLimit)
typeIdx++ ;
if (v & (1 << (bitLimit - bitNum - 1)))
typeIdx++;
else
else
set ~= typeIdx ;
set ~= typeIdx;
return set ;
return set;
}
}
}
}


// for finite Random Access Range
// For finite Random Access Range
auto combRep(R)(R types, uint numChoice)
auto combRep(R)(R types, in uint numChoice) /*pure nothrow*/
if(hasLength!R && isRandomAccessRange!R) {
if (hasLength!R && isRandomAccessRange!R) {
ElementType!R[][] result ;
ElementType!R[][] result;

foreach(s ; CombRep(types.length, numChoice)) {
foreach (s; CombRep(types.length, numChoice)) {
ElementType!R[] r ;
foreach(i ; s)
ElementType!R[] r;
r ~= types[i] ;
foreach (i; s)
result ~= r ;
r ~= types[i];
⚫
result ~= r;
}
}

return result ;
return result;
}
}


void main() {
void main() {
foreach(e;combRep(["iced","jam","plain"],2))
foreach (e; combRep(["iced", "jam", "plain"], 2))
writefln("%5s", e) ;
// writefln("%5s", e);
writeln(e);
writefln("Ways to select 3 from 10 types is %d", CombRep(10,3).length) ;
writeln("Ways to select 3 from 10 types is ",
CombRep(10, 3).length);
}</lang>
}</lang>
output:
output:
<pre>[ iced, iced]
<pre>["iced", "iced"]
[ iced, jam]
["iced", "jam"]
[ iced, plain]
["iced", "plain"]
[ jam, jam]
["jam", "jam"]
[ jam, plain]
["jam", "plain"]
[plain, plain]
["plain", "plain"]
Ways to select 3 from 10 types is 220</pre>
Ways to select 3 from 10 types is 220</pre>


Retrieved from "https://rosettacode.org/wiki/Combinations_with_repetitions"