Any improvements on this combination generator. Seen a lot of combination generators online, but none like this. Found pseudocode at: https://www.baeldung.com/cs/generate-k-combinations

Fastest I could make, make it FASTER if you can. Also appreciate improvements in code structure and oop, fairly new on c#.

public class CombinationGeneratorTwo
        private static int j = 1;
        private static bool TryIncrease(int[] combination)
            if(combination[j] + 1 < combination[j+1])
                    combination[j-1] = combination[j];
                    combination[j]= combination[j] + 1;
                    return true;           
            if(combination[2] >= j) return false;
            return TryDecrease(combination);

        private static bool TryDecrease(int[] combination)
            if(combination[j] > j)
                    combination[j] = combination[j -1];
                    combination[j-1] -= j -2;
                    return true;
            j+= 1;   
            return TryIncrease(combination);

        private static IEnumerator<int[]> VisitCombination(int[] combination)
                yield return combination;
                if (combination[0] > 1) 
                    combination[0] -= 1;

        public static void Main(int limit)
            // initialize
            var combination = new int[] { 1, 2, limit };

            var generator = VisitCombination(combination);
            while (generator.MoveNext())
                Console.WriteLine(string.Join(", ", generator.Current.Take(2)));
  • 4
    \$\begingroup\$ It would be nice to be able to paste this unmodified into an environment of choice and give it a spin: Please include all necessary using directives and "do something about Main(). \$\endgroup\$
    – greybeard
    May 20, 2022 at 5:05

2 Answers 2


From a design perspective, the state is split up a little awkwardly. Part of it is in the array that's passed around as an argument, and part of it is in the static int j. Static state is especially problematic since it means you can only run one of these iterators at a time. You might want a single object that contains all of the state. And you might want to explicitly follow the Iterator pattern (i.e. have a class that implements IEnumerable<>).

Relatedly, this is a little awkward:

var combination = new int[] { 1, 2, limit };

I understand that it's convenient for the algorithm to have limit at the end of the array, but it's a strange way for callers to pass that value in. As a caller, you would expect something more like:

foreach (var comb in new CombinationGenerator(limit))

As for performance, the algorithmic complexity is going to dominate here. Assuming you've chosen that wisely, the idea is to do as little extraneous work as possible. There might be a little room for improvement. This line:

string.Join(", ", generator.Current.Take(2))

is doing more work than it has to. I don't know if it ends up being measurable, but something like this will at least allocate fewer temporary values:

$"{generator.Current[0]}, {generator.Current[1]}"

Finally, static functions called Main are conventionally program entry points, and in that role need to take string[] args as their parameter. It's confusing to have a different signature even if it's legal in your situation.


The problems

I don't understand what your code does; and when I inspect individual components, I often end up confused and asking even more questions. This is a first indication of quality issues with the code. Or, to express it using the relevant source material:

enter image description here

StackExchange is not suited to a back-and-forth question time that I'd need to further understand this code, but I do want to list the proverbial WTFs here, as a measure of code quality and readability. I will then give you suggestions as to how to improve the readability.

  • What's a combination?
  • What does "up to a limit" mean?
  • What are we even trying to achieve here?
  • What does 1 and 2 express in new int[] { 1, 2, limit }?
  • What does limit express in new int[] { 1, 2, limit }?
  • Why is that array of 3 elements called a combination when the question mentions that you're looking for combination pairs? Pairs are two elements, not three.
  • Why is Main in a custom class?
  • Why did you create a non-static class that only contains static methods?
  • Why does TryIncrease end up calling TryDecrease?
  • Why does TryDecrease end up calling TryIncrease?
  • Has this code been vetted to not run into StackOverflowExceptions due to its nested recursion?
  • It is pretty much impossible to track how the value of j changes during the runtime of this logic. I'm not even sure what j conceptually expresses, let alone being able to understand how it subsequently affects the code.
  • I'm getting nervous about IndexOutOfRangeExceptions because of how convoluted it is to define j's value, yet your code seems to blindly assume that it can use j-1 and j+1 at specific times to access elements in a size 3 array.
  • I don't understand why your try methods are solely used to return a boolean which tells you something is possible, only for the VisitCombination method to then still have to generate the values on its own. It makes a lot more sense to have the try methods return the actual value (commonly done using an out parameter) to stop you from having to do the legwork twice.

This is not meant to be mean, in case it feels that way. I'm genuinely giving you my perception of your code, because I'm pretty sure you wrote this code in a way that makes sense to you, but with little consideration of how others would be able to interpret it.

This last bullet point, combined with the fact that you claim your code works; suggests to me that you did a lot of legwork to ensure that everything works the right way, but then failed to let your code actually reflect that work or document it in any way.

The improvements

In no particular order:

Unless contextually common, avoid single-letter variables such as j. While i is a common usage, it is generally used as a sequentially incrementing (or decrementing) index whose value is trivial to track, which is not the case for j.

Don't jam multiple parameters in a single array, because it's not clear what each value expresses. Given that you're looking for pairs, it makes more sense to pass separate parameters {1, 2} and limit, instead of merging them.

There is a whole lot of index juggling going on which are then used for boolean evaluations, and it's not clear what it is that you're actually evaluating. Using a named parameter can alleviate this issue, e.g.:

bool valuesAreEqual = combination[j-1] == combination[j];

    // do something

Alternatively, at the very least, use comments to explain code which is otherwise not trivial to understand.

while loops inherently come with a boolean evaluation to decide whether to repeat or not. Using while(true) and then doing if(evaluation) break; is needlessly complicating it.
I suspect you may have done so in order to ensure that the first loop always executes, but that is what a do while is for, i.e.:

    // my logic
    // guaranteed to run the first time
} while(evaluation);

// initialize is a bit of an irrelevant comment. There were many other things that could've done with an explanation, this wasn't really one of them.

Had you returned an IEnumerable<int[]> instead of a IEnumerator<int[]>, your iteration logic wouldn't have needed to manually operate the enumerator:

IEnumerable<int[]> pairs = VisitCombination(...);

foreach(int[] pair in pairs)
    // print the outcome

For the purpose of OOP, it would have made sense to define a Pair class to use instead of relying on the more primitive int[]. I'm avoiding explaining how to exactly change your code this way because I still don't quite understand the overall goal.

To summarize

There are more thing to fix here, but they rely on understanding the overall goal of the code which, even after studying this line by line, still isn't clear to me. I avoided telling you to improve things when I don't quite understand them because I'd be guessing.

The first order of business should be to improve the overall readability of your code. Change method and variable names to be more self-explanatory, avoid the reader having to decrypt your index number juggling because this is really hard to keep track of and interpret.

Try simplifying your logic, because my intuition is telling me that you've over-complicated something that could've been expressed much simpler.

  • \$\begingroup\$ Yes, you are correct on the code being wtf and having many standardized errors. Since I wrote this there were improvements, and there is yet more to improve. If you would like to understand what the algorithm is trying to achieve I recommend the link I posted(the revolving door algorithm). Thank you for your answer. \$\endgroup\$ Jul 17, 2022 at 10:07
  • \$\begingroup\$ Also if you know a more efficient algorithm to visit K Combinations I would appreciate it. I might be mistaken but I found this to be faster than the nested for loops. \$\endgroup\$ Jul 17, 2022 at 10:20
  • \$\begingroup\$ Saw python libraries that claimed to use this. \$\endgroup\$ Jul 17, 2022 at 10:21
  • \$\begingroup\$ Did not know about the do while, great! \$\endgroup\$ Jul 17, 2022 at 10:23
  • \$\begingroup\$ I also experience some speed gains when manually operating the enumerator and that is the reason I did that. Could be mistaken as well. \$\endgroup\$ Jul 17, 2022 at 10:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.