在运行时嵌套循环数 [英] Number of nested loops at runtime

问题描述

我试图输出所有可能的唯一整数组合，从1到最大为整数的整数。因此对于3个整数，最多4个我会得到：

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

123 124 134 234

我使用嵌套的for循环，但我想允许用户在运行时输入整数的数量。现在我有

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++);
...

有办法清理这个，所以我没有写出每个可能的整数for循环。

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

PS：我知道上面的代码不会输出请求的输出。这是一个编程竞争，所以我不是要求代码解决方案只是这个想法，这将使这成为可能。

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.

推荐答案

查看您对原始帖子的评论，您需要一个迭代解决方案。当你有一个支持尾调用优化的语言时，递归解决方案将与迭代解决方案一样快。但是，如果你使用Java / C＃，再次，这是不可用的，所以这里是另一种方式来看问题。

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.

您正在生成组合。组合只是具有一定数量的元素的子集。具有小ish集合的子集可以用位掩码表示。

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.

如果我有 [1，2，3，4] c $ c>并且我想描述子集 [1,3,4] ，我可以通过每个元素，并询问真或假：这是元素在子集中？因此，对于 [1,3,4] ，结果是 [True，False，True，True] 。如果我使用小于32（或64）字节的集合，我可以编码为一个整数：1011b = 11。这是非常紧凑的内存和计算机往往有非常快的bitmath操作符。

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.

那么，什么是组合，在这些二进制数字？如果我想要所有子集与N个成员，我可以翻译为我想要所有数字与N位设置。

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."

像我们一样，以 [1，2，3，4] 我们想要所有有3个元素的子集。有多少4位数字有正好3位设置？答案：1110b，1101b，1011b和0111b。如果我们把这些整数转换成子集，我们得到你的解决方案： [1，2，3] ， [1，2，4] c $ c>， [1,3,4] 和 [2,3,4] 。

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].

你可以开始思考比特。您从具有N位设置的最小数字开始。这对应于解决方案。然后你开始翻转位一对一。以系统的方式，每个迭代总是产生下一个最高的数字。

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.

这篇关于在运行时嵌套循环数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！