3

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

123 124 134 234

我正在使用嵌套的 for 循环执行此操作，但我希望允许用户在运行时输入整数的数量。现在我有

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

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

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

4

6 回答 6

3

一个词：递归。

于 2009-11-23T16:28:14.560 回答
1

使用递归，并numInts成为调用树的深度。

于 2009-11-23T16:28:26.790 回答
1

查看维基百科上的组合。这些是您试图生成的。

编辑：起初，我认为 OP 意味着排列。以下代码不适用于组合，但我会将其保留在此处，以防有人想对其进行调整以使其正常工作。

正如其他人所说，这是递归擅长的问题。让我们调用你的函数pick(num, list)。这是一些伪代码。

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
  }
}

上面代码的一些注释。注意这两种情况。递归几乎总是遵循基本案例/重复案例格式。实际递归发生在行results.add([item] + pick(num - 1, alteredList))中，关键是你通过了num-1。这意味着在每次调用 时pick，num都会变得越来越小，直到它到达1（当它到达时1，它就完成了）。

命名的变量alteredList被创建为列表的副本，删除了当前项目。大多数语言都有一个removed方法，但它会改变原始列表（这不是你想要的！！）当变量不可变时（当它们永远不会改变时），递归效果最好。

最后，我想澄清[item] + pick(num - 1, alteredList)一下。我的意思是创建一个新列表，其第一个元素是item，其余元素是 call 返回的列表pick(num - 1, alteredList)。在 Lisp 中，这种将元素添加到列表前面的操作称为 a cons。这个cons操作在函数式语言中非常强大，递归的使用非常频繁，但是用Java/C#等命令式语言来表达就很尴尬了。

于 2009-11-23T16:58:13.080 回答
1

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

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

如果我有集合[1, 2, 3, 4]并且我想描述子集[1, 3, 4]，我可以通过遍历每个元素并询问“True or False: is this element in the subset？”来做到这一点。所以，对于[1, 3, 4]，结果是[True, False, True, True]。如果我使用小于 32（或 64）字节的集合，我可以将其编码为整数：1011b = 11。这在内存中非常紧凑，并且计算机往往具有非常快速的位数学运算符。

那么，就这些二进制数而言，什么是组合呢？如果我想要所有具有 N 个成员的子集，我可以将其翻译为“我想要所有具有 N 位设置的数字”。

像[1, 2, 3, 4]我们一样。我们想要所有具有 3 个元素的子集。恰好设置了 3 位的 4 位数字有多少？答案：1110b、1101b、1011b 和 0111b。如果我们将这些整数转换为子集，我们会得到您的解：[1, 2, 3]、[1, 2, 4]、[1, 3, 4]和[2, 3, 4]。

您可以开始仅考虑位。您从设置了 N 位的最小数字开始。这对应于一个解决方案。然后，您开始一对一地翻转位。以一种系统的方式，使得每次迭代总是产生下一个最高的数字。

于 2009-11-23T17:12:07.153 回答
0 
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);
                }
            }
        }
    }
}
于 2009-11-23T16:34:47.463 回答
0

需要嵌套 for 循环的问题通常需要递归。

想象一棵树

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

然后穿过树（递归地）并收集“有效路径”

于 2009-11-23T16:39:07.703 回答