The number of nested loops at runtime

Question

I try to print all possible unique integer combinations from 1 to max for a given number of integers. So for 3 integers and a maximum of 4, I would get:

123 124 134 234

I do this with nested loops, but I want to allow the user to enter 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 any way to clear this, so I don't need to write out every possible integer for the loop.

PS: I know that the code above does not output the requested output. This is for programming competitions, so I am not asking for code solutions just an idea that would make this possible.

Answer 1

Looking at your comments on the original post, you want an iterative solution. A recursive solution will be as fast as an iterative solution if you have a language that supports tail call optimization. But if you are working with Java / C #, again, this is not available, so there’s another way to look at the problem.

You generate combinations. A combination is simply a subset with a certain number of elements. Subsets with small units can be expressed in bits.

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

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

Take [1, 2, 3, 4] as we were. We want all subsets with three elements. How many 4-bit numbers are there with 3 bits? Answer: 1110b, 1101b, 1011b and 0111b. If we translate 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 only by bits. You start with the smallest number with the N bits set. This is consistent with the decision. Then you start flipping bits one by one. Systematically, so that each iteration always leads to the next largest number.

Answer 2

One word: Recursion .

Answer 3

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

Answer 4

Check out the wikipedia combinations. This is what you are trying to create.

EDIT: At first, I thought OP meant permutation. The following code does not work for combinations, but I will save it here if someone wants to configure it to make it work.

As others have said, this is a problem for which recursion is superior. Let me call the pick(num, list) function. Here are some pseudo codes.

 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 to the above code. Note two cases. Recursion almost always matches the format of the base case / recursive case. The actual recursion happens on the line results.add([item] + pick(num - 1, alteredList)) , and the key point is that you go through num-1 . This means that with every call to pick , num gets smaller and smaller until it reaches 1 (when it reaches 1 , it was done).

A variable named alteredList is created as a COPY of the list with the current item deleted. Most languages ​​have a removed method, but it ALTERS from the original list (this is not what you want !!) Recursion works best when variables are immutable (when they never change).

Finally, I want to clarify the line [item] + pick(num - 1, alteredList) . I just want to create a new list, the first element of which is item , and the rest of the elements is the list returned by calling pick(num - 1, alteredList) . In Lisp, this operation of adding an item to the top of the list is called cons . This cons operation is extremely efficient in functional languages ​​where recursion is heavily used but inconvenient to express in imperative languages ​​like Java / C #.

Answer 5

 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 6

Problems in which you need nested for-loops usually scream about recursion.

Imagine a tree like

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

then go through the tree (recursively) and collect the "valid paths"