Number of nested loops at runtime

Question

I am trying to output all the possible unique integer combinations from 1 to max for a set number of integers. So for 3 integers and a max of 4 I would get:

123 124 134 234

I am doing this with nested for loops but I want to allow the user to input the number of integers at runtime. right now I have

if(numInts >6);
for(int x = 1; x < max; x++);
if(numInts >5);
for(int y = 1; y < max; y++);
...

Is there a way to clean this up so I don't have to write out each possible integer for loop.

PS: I know the code above will not output the requested output. This is for a programing competition so I am not asking for code solutions just the idea that would make this possible.

Answer 1

One word: Recursion.

Answer 2

Use recursion, and numInts becomes the depth of your call tree.

Answer 3

internal class Program {
    private static void Main(string[] args) {
        foreach (var combination in AllCombinations(new[] { 1, 2, 3 })) {
            Console.WriteLine(string.Join("", combination.Select(item => item.ToString()).ToArray()));
        }
    }

    private static IEnumerable<IEnumerable<T>> AllCombinations<T>(IEnumerable<T> elements) {
        if (elements.Count() == 1) yield return new[] { elements.First() };
        else {
            foreach (var element in elements) {
                foreach (var combination in AllCombinations(elements.Except(new[] { element }))) {
                    yield return (new[] { element }).Concat<T>(combination);
                }
            }
        }
    }
}

Answer 4

Problems where you would need nested for-loops usually shout for recursion.

Imagine a tree like

<root>
    <1>
       <1>
          <1>
          <2>
          <3>
          <4>
       <2>
          <1>
          <2>
          <3>
          <4>
    ...

then walk through the tree (recursivly) and collect the 'valid paths'

Answer 5

i think this might help you

Answer 6

Check out combinations on Wikipedia. These are what you are trying to generate.

EDIT: At first, I thought the OP meant permuations. The following code doesn't work for combinations, but I'll keep it here in case someone wants to tweak it to get it to work.

As others have said, this is a problem for which recursion excels at. Let's call your function pick(num, list). Here is some pseudo code.

List pick(Int num, List list)
{
  if (num == 1) // base case
  {
    return list
  }
  else // recurring case
  {
    var results = []
    foreach (item in list)
    {
      alteredList = list.copy().remove(item)
      results.add([item] + pick(num - 1, alteredList))
    }
    return results
  }
}

Some notes on the above code. Note the two cases. Recursion almost always follows the base-case/recurring-case format. The actual recursion occurs in the line results.add([item] + pick(num - 1, alteredList)), and the key point is that you pass num-1. This means that in each call to pick, num gets smaller and smaller until it reaches 1 (when it reaches 1, it's done).

The variable named alteredList is created as a COPY of list with the current item removed. Most languages have a removed method, but it ALTERS the original list (this is not what you want!!) Recursion works best when variables are immutable (when they aren't altered ever).

Lastly, I want to clarify the line [item] + pick(num - 1, alteredList) a bit. I simply mean create a new list, whose first element is item and the rest of the elements are the list returned by the call pick(num - 1, alteredList). In Lisp, this operation of adding an element to the front of a list is called a cons. This cons operation is extremely powerful in functional languages, where recursion is heavily used, but it is awkward to express in imperative languages, such as Java/C#.

Answer 7

Looking at your comments on the original post, you want an iterative solution. A recursive solution will be just as fast as an iterative solution when you have a language that supports tail call optimization. But if you're working with Java/C#, again, this isn't available, so here's another way to look at the problem.

You are generating combinations. A combination is just a subset with a certain number of elements. Subsets with small-ish sets can be expressed with bitmasks.

If I have the set [1, 2, 3, 4] and I want to describe the subset [1, 3, 4], I can do so by going through each element and asking "True or False: is this element in the subset?" So, for [1, 3, 4], the result is [True, False, True, True]. If I am working with a set less than 32 (or 64) bytes, I can encode this as an integer: 1011b = 11. This is very compact in memory and computers tend to have very fast bitmath operators.

So what is a combination then, in terms of these binary numbers? If I want all subsets with N members, I can translate that as "I want all numbers with N bits set."

Take [1, 2, 3, 4] as we have been. We want all subsets with 3 elements. How many 4-bit numbers are there with exactly 3 bits set? Answer: 1110b, 1101b, 1011b, and 0111b. If we turn these integers into subsets, we get your solutions: [1, 2, 3], [1, 2, 4], [1, 3, 4], and [2, 3, 4].

You can start thinking in terms of the bits only. You start off with the lowest number with N bits set. That corresponds to a solution. You then start flipping bits one-for-one. In a systematic way such that each iteration always results in the next highest number.