运行时的嵌套循环数

Recursion .

使用递归,然后 numInts

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

如果我有这套 [1, 2, 3, 4] [1, 3, 4] ,我可以通过检查每个元素并询问“True或False:这个元素在子集中吗?”来实现这一点 [1, 3, 4] [True, False, True, True] . 如果我使用的集合小于32(或64)字节,我可以将其编码为整数:1011b=11。这是非常紧凑的内存和计算机往往有非常快的位数学运算符。

那么,对于这些二进制数来说,组合是什么呢?如果我希望所有子集都有N个成员,我可以将其转换为“我希望所有数字都有N个位集”

[1, 2, 3, 4] [1, 2, 3] , [1, 2, 4] , ,及 [2, 3, 4] .

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

编辑:起初,我认为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 其余的元素是调用返回的列表 pick(num - 1, alteredList) cons 欺骗 操作在函数式语言中非常强大,在函数式语言中大量使用递归,但在命令式语言(如Java/C#)中很难表达。

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

然后遍历树(递归)并收集“有效路径”

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