For one of my projects, I need to produce all combinations where you choose k objects, having n possible objects to choose from. I have two uses for this, one where I need to produce all combinations of numbers, and one where I need to produce all combinations of Objects.
However we're talking k=27, n=20 which is a very big number, taking me 5 hours alone to run in a simple for loop. That is why I need a non recursive algorithm.
Also I need to only get the combinations that are ordered from left to right, the smallest number being to the left. So if k=3 and n=4, it would produce the following combinations:
1111
1112
1113
1114
1122
1123
1124
1222
1223
1224
1233
1234
1333
1334
1344
1444
2222
2223
2224
2233
2234
2244
2333
2334
2344
2444
3333
3334
3344
3444
4444
I realize that running such an algorithm would take days, maybe weeks with k=27, n=20, but time is not a problem for me in this case. But I would prefer to use a non recursive algorithm because that would after all be faster.
I have seen plenty of algorithms for producing permutations without repetitions but none for combinations with repetitions, so I can't really use those algorithms for much.
So what I would like help with, is a nudge, a push, something to help me get started on developing such an algorithm that can work equally well on both primitive types and Objects. I'm sure I'm not the first one to need to produce these results, and I'm sure someone out there has an idea for how to go about with this, as I have absolutely none.