创建所有可能的数组而不嵌套for循环

我想生成所有可能的长度为n数字，并且我的数字的每个数字都有一个来自集合{1,2,...,n-1}作为数组。 换句话说，我想列出长度为n且不包括0所有基数n 。

现在，我能想到的唯一方法是嵌套n for循环，并使用第（i + 1）个循环分配myArray[i] ，即

 int n; int[] myArray = new int[n]; for (int i1 = 1; i1 < n; i1++) myArray[0]=i1; for (int i2 = 1; i2 < n; i2++) myArray[1]=i2; // and so on.... for (int in = 1; in < n; in++) { myArray[n]=in; foreach (var item in myArray) Console.Write(item.ToString()); Console.Write(Environment.NewLine); } 

然后在最里面的循环打印每个数组。 显而易见的问题是，对于每个n，我需要手动编写n for循环。

从我所读到的，递归似乎是替换嵌套for循环的最佳方法，但我似乎无法弄清楚如何为递归制作一般方法。

编辑

例如，如果n=3 ，我想写出1 1 1 1 2 1 1 2 2 2 1 1 2 1 2 2 2 1 2 2 2 。

我们不限于n<11 。 例如，如果n=11 ，我们将输出

 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 3 ... 1 1 1 1 1 1 1 1 1 1 10 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 2 2 1 1 1 1 1 1 1 1 1 2 3 ... 1 1 1 1 1 1 1 1 1 9 10 1 1 1 1 1 1 1 1 1 10 1 1 1 1 1 1 1 1 1 1 10 2 1 1 1 1 1 1 1 1 1 10 3 ... 10 10 10 10 10 10 10 10 10 9 10 10 10 10 10 10 10 10 10 10 10 1 10 10 10 10 10 10 10 10 10 10 2 ... 10 10 10 10 10 10 10 10 10 10 10 

因此，数字的数字可以是1到10之间的任何值。 数组myArray只是用于获取其中一个数字，然后我们打印它，然后继续下一个数字并重复。

Answer 1

一如既往，在考虑递归解决方案时，尝试使用不可变结构来解决问题; 一切都更容易理解。

首先，让我们自己构建一个快速的小不可变堆栈，它将帮助我们跟踪我们当前生成的数量（同时不必担心在递归调用中生成的其他数字…记住，不可变数据可以’改变！）：

 public class ImmutableStack: IEnumerable { public static readonly ImmutableStack Empty = new ImmutableStack(); private readonly T first; private readonly ImmutableStack rest; public int Count { get; } private ImmutableStack() { Count = 0; } private ImmutableStack(T first, ImmutableStack rest) { Debug.Assert(rest != null); this.first = first; this.rest = rest; Count = rest.Count + 1; } public IEnumerator GetEnumerator() { var current = this; while (current != Empty) { yield return current.first; current = current.rest; } } public T Peek() { if (this == Empty) throw new InvalidOperationException("Can not peek an empty stack."); return first; } public ImmutableStack Pop() { if (this == Empty) throw new InvalidOperationException("Can not pop an empty stack."); return rest; } public ImmutableStack Push(T item) => new ImmutableStack(item, this); IEnumerator IEnumerable.GetEnumerator() => GetEnumerator(); } 

这很简单。 请注意堆栈如何重用数据。 在我们的小程序中会有多少空的不可变结构？ 只有一个。 并且包含序列1->2->4堆栈？ 是的，只有一个。

现在，我们实现一个递归函数，只是不断向堆栈添加数字，直到我们达到“纾困”状态。 哪个是？ 当堆栈包含n元素时。 十分简单：

 private static IEnumerable generateNumbers(ImmutableStack digits, IEnumerable set, int length) { if (digits.Count == length) { yield return int.Parse(string.Concat(digits)); } else { foreach (var digit in set) { var newDigits = digits.Push(digit); foreach (var newNumber in generateNumbers(newDigits, set, length)) { yield return newNumber; } } } } 

好的，现在我们只需要将它与我们的公共方法联系在一起：

  public static IEnumerable GenerateNumbers(int length) { if (length < 1) throw new ArgumentOutOfRangeException(nameof(length)); return generateNumbers(ImmutableStack.Empty, Enumerable.Range(1, length - 1).Select(d => d.ToString(CultureInfo.InvariantCulture)), length); } 

果然，如果我们称之为：

  var ns = GenerateNumbers(3); Console.WriteLine(string.Join(Environment.NewLine, ns.Select((n, index) => $"[{index + 1}]\t: {n}"))); 

我们得到了预期的输出：

 [1] : 111 [2] : 211 [3] : 121 [4] : 221 [5] : 112 [6] : 212 [7] : 122 [8] : 222 

请注意，生成的指定长度n的总数是(n - 1) ^ n ，这意味着对于相对较小的length值，您将获得相当多的数字生成; n = 10生成3 486 784 401 …