-
-
Save Minoru/745a7c19c7fa77702332cf4bd3f80f9e to your computer and use it in GitHub Desktop.
Helping Ender iterate through combinations of items
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
this helped me a lot, thanks.