创建所有可能的数组，而不嵌套for循环 [英] Creating all possible arrays without nested for loops
问题描述
我想生成所有可能的长度为 n 的数字，我的数字的每个数字都有一个来自集合 {1， 2，...，n-1} ，作为一个数组。换句话说，我想列出所有 n 长度 n 不包含<$ c
$ b
现在我唯一能想到的方法就是将n 嵌套到循环，并且使用第（i + 1）个循环来赋值 myArray [i] ，即
int n;
int [] myArray = new int [n];
for（int i1 = 1; i1
for（int i2 = 1; i2< n; i2 ++）
myArray [1] = i2;
//等等...
for（int in = 1; in< n; in ++）
{
myArray [n] = in;
foreach（myArray中的变量）
Console.Write（item.ToString（））;
Console.Write（Environment.NewLine）;
}
然后在最里面的循环打印每个数组。显而易见的问题是，对于每个n，我需要为循环手动编写 n 。
从我读过的看来，递归似乎是替换循环的嵌套 例如， ，如果 我们不限于 所以，数字的一个数字可以是的最好方法，但我似乎无法弄清楚编辑
n = 3 ，我想写出 1 1 1 ， 1 1 2 ， 1 2 1 ， 1 2 2 ， 2 1 1 ， 2 1 2 ， 2 2 1 ， 2 2 2 。
n <11 。例如，如果 n = 11 ，我们会输出
11 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 10 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 2
...
10 10 10 10 10 10 10 10 10 10
1 和 10 。数组 myArray 仅用于获取这些数字中的一个，然后打印出来，然后继续下一个数字并重复。
<与往常一样，当在递归解决方案中思考时，尝试使用不可变结构来解决问题;因此，首先，让我们建立一个快速的小不变的堆栈，这将帮助我们跟踪我们目前正在生成的数量（while不用担心在递归调用中会产生什么其他的数字，记住，不可变的数据不能改变！）：
$ p $ $ $ $ $ $ > public class ImmutableStack< T>：IEnumerable< T>
{
public static readonly ImmutableStack< T> Empty = new ImmutableStack< T>（）;
私人只读T第一;
private readonly ImmutableStack< T>休息;
public int Count {get; }
private ImmutableStack（）
{
Count = 0;
private ImmutableStack（T first，ImmutableStack< T> rest）
{
Debug.Assert（rest！= null）;
this.first = first;
this.rest =休息;
Count = rest.Count + 1;
}
public IEnumerator< T> GetEnumerator（）
{
var current = this;
while（current！= Empty）
{
yield return current.first;
current = current.rest;
$ b $ public T Peek（）
{
if（this == Empty）
throw new InvalidOperationException（Can not偷看一个空的堆栈）;
首先返回;
}
public ImmutableStack< T> Pop（）
{
if（this == Empty）
抛出新的InvalidOperationException（不能弹出空的堆栈。
return rest;
}
public ImmutableStack< T>推（T item）=> new ImmutableStack< T>（item，this）;
IEnumerator IEnumerable.GetEnumerator（）=>的GetEnumerator（）;
}
这很简单。请注意堆栈如何重用数据。我们的小程序中会有多少空的不可改变的结构？只有一个。包含序列 1-> 2-> 4 的堆栈是的，只有一个。
现在我们实现一个递归函数，直到我们达到我们的保释条件时才向栈中添加数字。哪个？当堆栈包含 n 元素时。简单易懂：
private static IEnumerable< int> generateNumbers（ImmutableStack< string>数字，IEnumerable< string> set，int的长度）
{
if（digits.Count == length）
{
yield return int.Parse string.Concat（位））;
{
foreach（var中的数字）
{
var newDigits = digits.Push（digit）;
foreach（newNumber in generateNumbers（newDigits，set，length））
{
yield return newNumber;
好的，现在我们只需要将它们与我们的公共方法结合在一起：
public static IEnumerable< int> GenerateNumbers（int length）
{
if（length <1）
throw new ArgumentOutOfRangeException（nameof（length））;
$ b返回generateNumbers（ImmutableStack< string> .Empty，
Enumerable.Range（1，length - 1）.Select（d => d.ToString（CultureInfo.InvariantCulture）），
长度）;
}
果然，如果我们称之为：
var ns = GenerateNumbers（3）;
Console.WriteLine（string.Join（Environment.NewLine，
ns.Select（（n，index）=> $[{index + 1}] \ t：{n}） ））;
我们得到预期的输出：
[1]：
[2]：211
[3]：121
[4]：221
[5]：112
[6]：212
[7]：122
[8]：222
请注意，指定长度 n 所产生的数字总数是（n - 1）^ n 这意味着对于 n = 10 生成3 486 784 401 ...
I would like to generate all the possible numbers that have length n and each digit of my number has a value from the set {1,2,...,n-1}, as an array. In other words, I would like to list all the base n numbers with length n that do not include 0.
Right now, the only way I can think to do it is by nesting n for loops, and assigning myArray[i] with the (i+1)th loop, i.e.
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);
}
and then printing each array at the innermost loop. The obvious issue is that for each n, I need to manually write n for loops.
From what I've read, recursion seems to be the best way to replace nested for loops, but I can't seem figure out how to make a general method for recursion either.
EDIT
For example, if n=3, I would like to write out 1 1 1, 1 1 2, 1 2 1, 1 2 2, 2 1 1, 2 1 2, 2 2 1, 2 2 2.
We are not limited to n<11. For example, if n=11, we would output
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
So, a digit of a number may be any value between and including 1 and 10. The array myArray is simply used to get one of these numbers, then we print it, and go on to the next number and repeat.
As always, when thinking in recursive solutions, try to solve the problem using immutable structures; everything is much simpler to understand.
So first of all, lets build ourselves a fast little immutable stack that will help us keep track of the number we are currently generating (while not worrying about what other numbers are being generated in the recursive call...remember, immutable data can't change!):
public class ImmutableStack<T>: IEnumerable<T>
{
public static readonly ImmutableStack<T> Empty = new ImmutableStack<T>();
private readonly T first;
private readonly ImmutableStack<T> rest;
public int Count { get; }
private ImmutableStack()
{
Count = 0;
}
private ImmutableStack(T first, ImmutableStack<T> rest)
{
Debug.Assert(rest != null);
this.first = first;
this.rest = rest;
Count = rest.Count + 1;
}
public IEnumerator<T> 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<T> Pop()
{
if (this == Empty)
throw new InvalidOperationException("Can not pop an empty stack.");
return rest;
}
public ImmutableStack<T> Push(T item) => new ImmutableStack<T>(item, this);
IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
}
That's easy. Note how the stack reuses data. How many empty immutable structs will there be in our little program? Only one. And stacks containing the sequence 1->2->4? Yup, only one.
Now, we implement a recursive function that just keeps adding numbers to the stack until we reach our "bail out" condition. Which is? When the stack contains n elements. Easy peasy:
private static IEnumerable<int> generateNumbers(ImmutableStack<string> digits, IEnumerable<string> 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;
}
}
}
}
Ok, and now we just need to tie it alltogether with our public method:
public static IEnumerable<int> GenerateNumbers(int length)
{
if (length < 1)
throw new ArgumentOutOfRangeException(nameof(length));
return generateNumbers(ImmutableStack<string>.Empty,
Enumerable.Range(1, length - 1).Select(d => d.ToString(CultureInfo.InvariantCulture)),
length);
}
And sure enough, if we call this thing:
var ns = GenerateNumbers(3);
Console.WriteLine(string.Join(Environment.NewLine,
ns.Select((n, index) => $"[{index + 1}]\t: {n}")));
We get the expected output:
[1] : 111
[2] : 211
[3] : 121
[4] : 221
[5] : 112
[6] : 212
[7] : 122
[8] : 222
Do note that the total amount of numbers generated of a specified length n is (n - 1) ^ n which means that for relatively small values of length you are going to get quite an amount of numbers generated; n = 10 generates 3 486 784 401...
这篇关于创建所有可能的数组，而不嵌套for循环的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
