Skip to content

Instantly share code, notes, and snippets.

@Minoru

Minoru/ender.cpp Secret

Created December 23, 2016 14:39
Show Gist options
  • Save Minoru/745a7c19c7fa77702332cf4bd3f80f9e to your computer and use it in GitHub Desktop.
Save Minoru/745a7c19c7fa77702332cf4bd3f80f9e to your computer and use it in GitHub Desktop.
Helping Ender iterate through combinations of items
#include <iostream>
using namespace std;
static long FactNaive(int n)
{
long r = 1;
for (int i = 2; i <= n; ++i)
r *= i;
return r;
}
static long long CrNK (long n, long k)
{
long long u, l;
u = FactNaive(n+k-1);
l = FactNaive(k)*FactNaive(n-1);
return u/l;
}
int main()
{
int numberOFchoices=4,kountOfElementsInCombination=3;
int arrayOfSingleCombination[kountOfElementsInCombination] = {0,0,0};
int arrayIndexOfIncrementation,bIfIeverNeedIt;
arrayIndexOfIncrementation=bIfIeverNeedIt=kountOfElementsInCombination-1;
// By default, this points to a position behind last element, indicating
// that no resets are necessary
int leftmostResetPos = kountOfElementsInCombination;
for (long long i = 0; i < CrNK(numberOFchoices, kountOfElementsInCombination); i++)
{
leftmostResetPos = kountOfElementsInCombination;
if (i != 0)
{
arrayOfSingleCombination[arrayIndexOfIncrementation]++;
for (int j = kountOfElementsInCombination-1; j > 0; j--)
{
if(arrayOfSingleCombination[j] == numberOFchoices)
{
// we're iterating through j in descending order, so no
// checks are necessary - j is moving from right to left
leftmostResetPos = j;
// the value of arrayOfSingleCombination[j] will be reset
// later
arrayOfSingleCombination[j-1]++;
}
}
}
if (leftmostResetPos != kountOfElementsInCombination) {
arrayIndexOfIncrementation = kountOfElementsInCombination - 1;
int resetValue = 1;
for (int j = 0; j < leftmostResetPos; j++) {
if (arrayOfSingleCombination[j] > resetValue) {
resetValue = arrayOfSingleCombination[j];
}
}
for (int j = leftmostResetPos; j != kountOfElementsInCombination; j++) {
arrayOfSingleCombination[j] = resetValue;
}
}
for (int j = 0; j<kountOfElementsInCombination; j++)
{
cout<<arrayOfSingleCombination[j]<<" ";
}
cout<<"\n";
}
return 0;
}
@EnderEyre
Copy link

this helped me a lot, thanks.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment