运行时嵌套循环的数量

6 回答

• 1

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

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

  如果我有设置 [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个元素的子集 . 有多少个4位数字，正好设置了3位？答案：1110b，1101b，1011b和0111b . 如果我们将这些整数转换为子集，我们会得到您的解决方案： [1, 2, 3] ， [1, 2, 4] ， [1, 3, 4] 和 [2, 3, 4] .

  你可以开始只考虑比特 . 从N位设置的最低编号开始 . 这对应于一个解决方案 . 然后，您开始一对一地翻转位 . 以系统的方式使得每次迭代总是导致下一个最高的数字 .

  回复于 2024-04-24T16:52:29+08:00
• 0

  一个字： Recursion .

  回复于 2024-04-24T16:52:29+08:00
• 1

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

  回复于 2024-04-24T16:52:29+08:00
• 3

  查看维基百科上的组合 . 这些是你想要产生的 .

  编辑：起初，我认为OP意味着permeations . 以下代码不适用于组合，但我会保留它，以防有人想要调整它以使其工作 .

  正如其他人所说，这是递归擅长的问题 . 我们来调用你的函数 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 的变量创建为列表的COPY，并删除当前项 . 大多数语言都有一个 removed 方法，但它改变了原始列表（这不是你想要的！）当变量是不可变的时（当它们不被改变时），递归效果最好 .

  最后，我想澄清一下 [item] + pick(num - 1, alteredList) 这一行 . 我只是意味着创建一个新列表，其第一个元素是 item ，其余元素是调用 pick(num - 1, alteredList) 返回的列表 . 在Lisp中，将一个元素添加到列表前面的操作称为 cons . 这种 cons 操作在函数式语言中非常强大，其中递归被大量使用，但是用命令式语言表达是很尴尬的，例如Java / C＃ .

  回复于 2024-04-24T16:52:29+08:00
• 1

  你需要嵌套for循环的问题通常是为了递归而大喊大叫 .

  想象一棵树就像

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

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

  回复于 2024-04-24T16:52:29+08:00
• 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);
                  }
              }
          }
      }
  }
  

  回复于 2024-04-24T16:52:29+08:00