After seeing this thread http://forums.cgsociety.org/showthread.php?f=98&t=1497948 I wonder what would be the better way to do it (or other similar problem) for a non-previous determined number of items. In this case it was for 5 items, so the problem is solved with 5 hard-coded loops inside loops.
I have fighted a little searching a solution and it’s really no intuitive.
So, here’s the challenge: given a number ‘maxNum’, find all the non-repetitive combinations of ‘numItems’ items with values from 1 to ‘maxNum’ (of course, numItems <= maxNum).
Extra points for giving a sorted result.
Example: for ‘maxNum’ = 7 and ‘numItems’ = 5, these are the 21 possible combinations:
#(1, 2, 3, 4, 5)
#(1, 2, 3, 4, 6)
#(1, 2, 3, 4, 7)
#(1, 2, 3, 5, 6)
#(1, 2, 3, 5, 7)
#(1, 2, 3, 6, 7)
#(1, 2, 4, 5, 6)
#(1, 2, 4, 5, 7)
#(1, 2, 4, 6, 7)
#(1, 2, 5, 6, 7)
#(1, 3, 4, 5, 6)
#(1, 3, 4, 5, 7)
#(1, 3, 4, 6, 7)
#(1, 3, 5, 6, 7)
#(1, 4, 5, 6, 7)
#(2, 3, 4, 5, 6)
#(2, 3, 4, 5, 7)
#(2, 3, 4, 6, 7)
#(2, 3, 5, 6, 7)
#(2, 4, 5, 6, 7)
#(3, 4, 5, 6, 7)
(Edit) Mathematical note: the number of possible combinations is (maxNum! / (numItems! * (numMax – numItems)!)), so be prudent with your testing values.
fn compIterator start level:1 maxnum: count: item: buffer: limit: =
(
item[level] = start
if buffer.count < limit do
(
if level == count then append buffer (deepcopy item)
else
(
for k = start + 1 to maxnum do
(
compIterator k level:(level + 1) maxnum:maxnum count:count item:item buffer:buffer limit:limit
)
)
)
)
fn getUniqueCombinations maxnum count limit:100000 =
(
buffer = #()
item = #()
item.count = count
for i = 1 to maxnum do compIterator i maxnum:maxnum count:count item:item buffer:buffer limit:limit
buffer
)
/*
compIterator()
vv = getUniqueCombinations 20 6
for v in vv do format "%
" v
*/
This is called permutation and is trivially achieved using recursion.
(
local maxNum = 7
local numItems = 5
fn concat results& arr num =
(
if (arr.count == numItems or num > maxNum) then
(
append results arr
)
else
(
for i = num + 1 to maxNum do
(
local a = deepcopy arr
append a i
concat results a i
)
)
)
local arr = #()
local results = #()
concat results arr 0
for r in results do print (r as string)
)
Yes, recursion is the key.
Both solutions are very similar and give the same time results (a little better DenisT’s one, depending on maxNum and numItems values).
Both have the same “issue”: they try numbers that are not possible. These are all numbers that meet: value > (maxnum – numItems + position +1)
The higher the ‘numItems’ value, the higher the number of not possible values tried.
Modifying DenisT’s code with:
for k = start + 1 to (maxnum - count + level + 1) do
these are the time test results:
-
maxNum = 20; numItems = 5 (15.504 combinations)
@lo time: 78ms / Memory used= 1.574.162L
@DenisT time: 78ms / Memory used= 1.128.122L
@DenisT modified time: 75ms / Memory used= 1.128.122L -
maxNum = 20; numItems = 7 (77.520 combinations)
@lo time: 490ms / Memory used= 9.946.322L
@DenisT time: 480ms / Memory used= 5.593.274L
@DenisT modified time: 423ms / Memory used= 5.593.274L -
maxNum = 20; numItems = 10 (184.756 combinations)
@lo time: 2.345ms / Memory used= 26.143.806L
@DenisT time: 2.060ms / Memory used= 13.314.266L
@DenisT modified time: 1.288ms / Memory used= 13.314.266L -
maxNum = 20; numItems = 12 (125.970 combinations) – Here it gets worse as number of combinations begins to be lower
@lo time: 3.584ms / Memory used= 23.030.206L
@DenisT time: 2.967ms / Memory used= 9.081.674L
@DenisT modified time: 1.068ms / Memory used= 9.081.674L -
maxNum = 20; numItems = 14 (38.760 combinations)
@lo time: 4.067ms / Memory used= 22.237.726L
@DenisT time: 3.291ms / Memory used= 2.802.554L
@DenisT modified time: 427ms / Memory used= 2.802.554L
theres a function for this in the STL… called next_permutation
void PermGenerator(int n, int k)
{
std::vector<int> d(n);
std::iota(d.begin(),d.end(),1);
cout << "These are the Possible Permutations: " << endl;
do
{
for (int i = 0; i < k; i++)
{
cout << d[i] << " ";
}
cout << endl;
std::reverse(d.begin()+k,d.end());
} while (next_permutation(d.begin(),d.end()));
}
this is an algorithm for all possible permutations…
for all combinations I found ( https://stackoverflow.com/questions/12991758/creating-all-possible-k-combinations-of-n-items-in-c ):
void comb(int N, int K)
{
std::string bitmask(K, 1); // K leading 1's
bitmask.resize(N, 0); // N-K trailing 0's
// print integers and permute bitmask
do {
for (int i = 0; i < N; ++i) // [0..N-1] integers
{
if (bitmask[i]) std::cout << " " << i;
}
std::cout << std::endl;
} while (prev_permutation(bitmask.begin(), bitmask.end()));
}