Создание всех возможных массивов без вложенных циклов

Question

Я хотел бы сгенерировать все возможные числа, которые имеют длину n, и каждая цифра моего номера имеет значение из набора {1,2,...,n-1} в виде массива. Другими словами, я хотел бы перечислить все базовые номера n длиной n, которые не включают 0.

Прямо сейчас, единственный способ, которым я могу думать, чтобы сделать это путем вложения п for петель, и назначая myArray[i] с (я + 1) -го цикла, т.е.

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 мне нужно вручную написать nfor.

Из того, что я читал, рекурсия кажется лучшим способом заменить вложенные петли for, но я не могу понять, как сделать общий метод для рекурсии.

EDIT

Например, если 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, мы бы выход

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

Это очень просто. Обратите внимание, как стек повторно использует данные. Сколько пустых неизменяемых структур будет в нашей маленькой программе? Единственный. И стеки, содержащие последовательность 1->2->4? Да, только один.

Теперь мы реализуем рекурсивную функцию, которая просто добавляет числа в стек до тех пор, пока мы не достигнем нашего условия «спасения». Который? Когда стек содержит n элементов.Проще простого:

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

Хорошо, а теперь нам просто нужно, чтобы связать его ALLtogether с нашим общественным способом:

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

И действительно, если мы называем эту вещь:

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