Алгоритм нахождения последовательностей чисел в C#

Необходимо найти и вывести на экран все последовательности длины N из чисел 1,2,...,M. Это одна из типовых задач программирования, с которой, думаю, каждый хотя бы раз в том или ином виде сталкивался или столкнется при работе над каким-либо проектом. И в этой статье, посвященной различным алгоритмам, реализованным на языке C# мы и решим эту саму задачу о поиске всех возможных последовательностей.

Задача

Пользователь вводит с клавиатуры два числа: N — длину каждой последовательности, M — последнее число из ряда 1...M. Программа должна составить N последовательностей длиной N из ряда чисел 1..M.

Суть решения задачи

Чтобы понять, как должен выглядеть результат, представим задачу с конкретными значениями, например, N = 4, M = 3. Тогда наша программа должна составить и вывести следующие последовательности:

(1,1,1,1) (1,1,1,2) (1,1,1,3) (1,1,2,1) (3,1,3,3) (3,2,1,1)....(3,3,3,3)

Количество таких последовательностей всегда будет равно M^N.

Для решения задачи нам понадобятся следующие знания: что такое массив и работа с циклами.

Реализация алгоритма поиска последовательностей на C#

Ниже представлен код программы на C#, реализующий поиск и вывод всех последовательностей длиной N из ряда чисел 1..M

class Program
 {
     static void Main(string[] args)
     {
         byte m;
         byte n;
         byte[] Sequence;
         int counter = 1;

         Console.WriteLine("Введите количество элементов последовательности (N) и нажмите Enter");
         n = byte.Parse(Console.ReadLine());
         Console.WriteLine("Введите последнее число из ряда (1..M) и нажмите Enter");
         m = byte.Parse(Console.ReadLine());

         Sequence = new byte[n]; //массив в котором будет храниться очередная последовательность

         bool yes;
        
         void Next(byte[] sequence)
         {
             int i = n - 1;
             while ((i > -1) && (sequence[i] == m))
             {
                 sequence[i] = 1;
                 i--;
             }
             yes = i > -1;
             //если очередной элемент в последовательности можно нарастить
             if (yes)
             {
                 sequence[i]++;
             }
         }

         //задаем первую последовательность, например, (1,1,1,1)
         for (int i = 0; i < n; i++)
         {
             Sequence[i] = 1;
         }

         //пробуем перебрать все последовательности
         do
         {
             //выводим счётчик очередной последовательности (стартуем с 1)
             Console.Write($"{counter}: ");
             counter++;
             //выводим на экран очередную последовательность
             for (int i = 0; i < n; i++)
             {
                 Console.Write($"{Sequence[i]} ");
             }
             Console.WriteLine();
             //пробуем найти следующую последовательность
             Next(Sequence);
         }
         while (yes);

     }
 }

Результат работы программы представлен ниже:

Как видите, программа вывела ровно M^N (2^3 = 8) последовательностей.

Готовый проект C# вы можете скачать из нашего репозитория на GitHub.

Итого

Сегодня мы научились искать все последовательности заданной длины состоящие из чисел от 1 до M. В работе мы использовали массивы, циклы for, while и do..while и для вывода строк воспользовались интерполяцией.