Anonymous user
Combinations with repetitions: Difference between revisions
Updated D code
(→{{header|PHP}}: output) |
(Updated D code) |
||
Line 189:
=={{header|D}}==
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
/*immutable*/ const struct CombRep {
immutable uint nt, nc
private /*immutable*/ ulong[] combVal;
this(in uint numType, in uint numChoice) pure nothrow {
assert(0 < numType && numType + numChoice <= 64,
"valid only for nt + nc <= 64 (ulong bit size)")
nt = numType
nc = numChoice
if (nc == 0)
auto v = (1UL << (nt - 1)) - 1;
// init to smallest number that has nt-1 bit set
// a set bit is metaphored as a _type_ seperator
immutable limit = v << nc
//
// zero-bit a zero-bit means a _choice_ between _type_
while(v <= limit) {▼
//
while
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
}
uint[] opIndex(in uint idx) const pure nothrow {
return val2set(combVal[idx]);
}
int opApply(int delegate(ref uint[]) dg) {
foreach (v; combVal) {
auto set = val2set(v)
if (dg(set))
break
}
return 1
}
private uint[] val2set(in ulong v) const pure nothrow {
// convert bit pattern to selection set
immutable uint
uint
foreach
if (v & (1
typeIdx++;
else
set ~= typeIdx
return set
}
}
//
auto combRep(R)(R types, in uint numChoice) /*pure nothrow*/
if
ElementType!R[][] result
foreach (s
foreach
}
return result
}
void main() {
foreach (e; combRep(["iced", "jam", "plain"], 2))
// writefln("%5s", e)
writeln(e);
CombRep(10, 3).length);
}</lang>
output:
<pre>[
[
[
[
[
["plain", "plain"]
Ways to select 3 from 10 types is 220</pre>
| |||