Нерекурсивный алгоритм генерации перестановок

    Предлагаемый ниже нерекурсивный алгоритм несколько отличается от изложенных в книге Липского [1] и обнаруженных мной в русскоязычном сегменте интернета. Надеюсь будет интересно.

    Кратко постановка задачи. Имеется множество размерности N. Необходимо получить все N! возможных перестановок.
    Далее, для простоты, используем в качестве множества целые числа (1..N). Вместо чисел можно использовать любые объекты, т.к. операций сравнения элементов множества в алгоритме нет.
    Для хранения промежуточных данных сформируем структуру данных следующего вида:
      type dtree
         ukaz as integer       ' номер выбранного элемента в списке
         spisok() as integer  ' список доступных значений
       end type
    

    и заполним ее первоначальными значениями
     Dim masiv(N-) As dtree  ' размерность массива = N-1
     For ii = 1 To N - 1
       masiv(ii).ukaz = 1 
       ReDim masiv(ii).spisok(N + 1 - ii) ' устанавливаем размерность списка
       For kk = 1 To (N + 1 - ii)
         masiv(ii).spisok(kk) = kk + ii - 1
       Next
     Next
    

    Номер элемента в массиве masiv будем далее называть уровнем.
    В список первого уровня заносим все элементы множества. На первом уровне размерность списка равна N и сам список не изменяется по всему ходу выполнения алгоритма. При первичном заполнении все указатели в массиве устанавливаются на первый элемент в списке.
    На каждом следующем уровне его список формируется на основании списка предыдущего уровня, но без одного элемента, который помечен указателем. На предпоследнем уровне (N-2) список содержит три элемента. На последнем уровне (N-1) список содержит два элемента. Список нижнего уровня формируется как список предыдущего уровня без элемента, на который указывает указатель предыдущего уровня.
    В результате первичного заполнения получены две первых перестановки.Это общий массив сформированный на верхних уровнях ( 1… (N-2)) из элементов списка на которые указывают указатели.
    For ii = 1 To N-2
       massiv(ii).spisok(ukaz)
    Next
    

    и из списка последнего уровня- две пары элементов в разном порядке ( два хвостика 1 2 и 2 1)
    +   massiv(N-1).spisok(1) + massiv(N-1).spisok(2)
    +   massiv(N-1).spisok(2) + massiv(N-1).spisok(1)
    

    Все дальнейшие перестановки формируются также, всегда с предпоследнего уровня (N-2),
    Порядок получения последующих перестановок состоит в том, что находясь на предпоследнем уровне (N-2) и сформировав две перестановки пытаемся увеличить указатель выбранного элемента на 1.
    Если это возможно, то на последнем уровне меняем список и повторяемся.
    Если на предпоследнем уровне увеличить указатель не удается (перебраны все возможные варианты ), то поднимаемся до уровня на котором увеличение указателя (перемещение вправо) возможно. Условие окончания работы алгоритма — указатель на первом уровне выходит за N.
    После сдвига указателя вправо меняем список под ним и двигаемся вниз до предпоследнего уровня (N-2) также обновляя списки и устанавливая указатели выбранного элемента в 1.
    Более наглядно и понятно работа алгоритма представлена на рисунке ниже ( для размерности множества N =5). Номер на рисунке соответствует уровню в описании. Возможно даже, что кроме рисунка для понимания алгоритма ничего и не надо.

    Конечно, при реализации алгоритма можно было использовать и обычный двухмерный массив, тем более что для небольших N выигрыш объема памяти ничего не дает, а на больших N мы можем не дождаться окончания работы алгоритма.
    Один из способов реализации алгоритма на VBA ниже. Для его запуска можно создать книгу Excel с макросами, создать модуль на вкладке разработчик VB и скопировать текст в модуль. После запуска generate() на Лист1 будут выведены все перестановки.

    VBA для Excel

    Option Explicit
    Type dtree
      tek_elem_ukaz As Integer
      spisok() As Integer
     End Type
    Dim masiv() As dtree
    Dim start_print As Integer
    Dim N As Integer
    
    Sub generate()
     Dim ii As Integer, kk As Integer, jj As Integer
     Dim uroven  As Integer
     
     Лист1.Cells.Clear
     N = 5
     start_print = 1
     ReDim masiv(N - 1)
     '  первичное заполнение
     For ii = 1 To N - 1
       masiv(ii).tek_elem_ukaz = 1
       ReDim masiv(ii).spisok(N + 1 - ii)
       For kk = 1 To (N + 1 - ii)
         masiv(ii).spisok(kk) = kk + ii - 1
       Next
     Next
     uroven = N - 2
     Do
      ' результат
      Call print_rezult(uroven)
      ' на последнем уровне можно сдвинуться  вправо
      If masiv(uroven).tek_elem_ukaz <= (N - uroven) Then
       ' делаем шаг вправо
       ' меняем тек элемент
        masiv(uroven).tek_elem_ukaz = masiv(uroven).tek_elem_ukaz + 1
       ' меняем массив снизу
         Call zap_niz(uroven)
      Else
       ' делаем шаг вверх до первого уровня, где можно сдвинуться вправо
        Do While uroven > 1 And masiv(uroven).tek_elem_ukaz > (N - uroven)
          uroven = uroven - 1
        Loop
        If uroven = 1 And masiv(1).tek_elem_ukaz = N Then
           MsgBox "stop calc"
          Exit Sub ' напечатали все
        End If
       ' делаем шаг вправо на первом снизу доступном уровне
        masiv(uroven).tek_elem_ukaz = masiv(uroven).tek_elem_ukaz + 1
        Call zap_niz(uroven)
       ' заполнение нижних уровней
        Do While uroven < N - 2
          uroven = uroven + 1
          masiv(uroven + 1).tek_elem_ukaz = 1
          ' меняем массив снизу
          For kk = 2 To N - uroven + 1
            masiv(uroven + 1).spisok(kk - 1) = masiv(uroven).spisok(kk)
          Next
        Loop
      End If
     Loop
    End Sub
    
    Sub print_rezult(ukaz As Integer)
    Dim ii  As Integer
    For ii = 1 To ukaz
        With masiv(ii)
           Лист1.Cells(start_print, ii) = .spisok(.tek_elem_ukaz)
           Лист1.Cells(start_print + 1, ii) = .spisok(.tek_elem_ukaz)
        End With
    Next
        With masiv(ukaz + 1)
            Лист1.Cells(start_print, ukaz + 1) = .spisok(1)
            Лист1.Cells(start_print, ukaz + 2) = .spisok(2)
            start_print = start_print + 1
            Лист1.Cells(start_print, ukaz + 1) = .spisok(2)
            Лист1.Cells(start_print, ukaz + 2) = .spisok(1)
            start_print = start_print + 1
        End With
    End Sub
    
    Sub zap_niz(ukaz As Integer)
       ' заполнение нижнего уровня
    Dim ii As Integer, wsp1 As Integer
    ' меняем тек элемент
      wsp1 = masiv(ukaz).tek_elem_ukaz
      masiv(ukaz + 1).tek_elem_ukaz = 1
      ' меняем массив снизу
        For ii = 1 To wsp1 - 1
            masiv(ukaz + 1).spisok(ii) = masiv(ukaz).spisok(ii)
        Next
        For ii = wsp1 + 1 To N - ukaz + 1
            masiv(ukaz + 1).spisok(ii - 1) = masiv(ukaz).spisok(ii)
        Next
    End Sub
    
    


    Ссылки:
    [1] В.Липский. Комбинаторика для программистов. -Москва, издательство Мир, 1988.
    Поделиться публикацией
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама
    Комментарии 49
    • +1
      Один вопрос: зачем так сложно? Зачем вообще список?

      Не знаю, что там было написано у Липского — но за три простых цикла находится следующая перестановка. Осталось запустить этот алгоритм N! раз — и мы нашли все перестановки.
      int i = N - 2;
      while (i >= 0 && array[i] >= array[i+1]) i = i-1;
      
      if (i >= 0) {
          int j = i+1;
          while (array[i] < array[j+1]) j=j+1;
          int temp = array[i];
          array[i] = array[j];
          array[j] = temp;
      }
      
      for (int j = i+1, k = N-1; j < k; j=j+1, k=k-1) {
          int temp = array[j];
          array[j] = array[k];
          array[k] = temp;
      }
      
      return i>=0;
      


      PS код не запускал, он может содержать опечатки.
      • 0
        Нехорошо, что здесь используется сравнение элементов array. В общем случае, мы ищем перестановки произвольного множества, а на них порядка может и не быть.
        • 0
          В общем случае array — это массив индексов.
          • 0
            Значит, приходится тратить место на лишний массив. А вы попробуйте перебрать перестановки в одном массиве, без рекурсии, за O(1) дополнительной памяти и желательно, за O(N!) операций :) (за O((N+1)!) делается с помощью алгоритма из комментария ниже). Не уверен, впрочем, что это возможно…
            • +1
              Для номера текущей перестановки требуется отвести Θ(N log N) памяти — т.е. мой алгоритм просит даже меньше.
              • 0
                Действительно. Если хранить индексы в битовом массиве, реализованном на одной или двух целых переменных, то памяти будет примерно столько же.
                • +1
                  Упс… именно что столько же. Я допустил ту же самую ошибку, которую нашел в ваших рассуждениях )
                  • +1
                    Это скорее вопрос формализации задачи. Если всё честно считать в битах, то да, Θ(N log N) и там, и там. Более того, очевидно, что, если в основном массиве непонятно что записано и мы только меняем местами его элементы, это нижняя граница по дополнительной памяти (потому что всю информацию мы берем только из дополнительной памяти, значит перед началом генерации каждой перестановки в этой памяти должно быть записано своё уникальное значение, последовательностей N!, значит нам требует не меньше log2 N! бит).

                    Но по факту, N ограничено сверху очень маленькой константой порядка 20 (иначе алгоритм до нашей смерти не закончит работу), поэтому если уж так хочется сравнивать по памяти алгоритмы, то разумнее уж прямо в байтах написать, сколько кому требуется, а не асимптотики сравнивать.
              • 0
                Нет, возможно:

                void RepSeq(T *A,int N){
                	for(int ind=1;;ind++){
                                PrintPerm(A,N);
                		int a=ind,p=0,j;
                		for(j=N;j>0;j--){
                			int x=a%j; a/=j;
                			if(x){
                				if(a%2) x=j-x;
                				swap(A+p-1+x,A+p+x);
                				break;
                			} else p+=1-a%2;
                		}
                		if(!j) break;
                	}
                }
                
                • +1
                  Да, я тоже думал в эту сторону, но остановился на понимании того, что переменная ind в любом случае займет Θ(N log N) памяти асимптотически. А lemelisk даже объяснил, почему это ограничение никак не обойти.
          • 0
            Я немного извиняюсь, но в моем контексте список это тоже массив. Сложности в алгоритме не вижу, рисунок, как мне кажется, достаточно нагляден. Я рассматриваю алгоритм как попытку рекурсию «засунуть» в данные и тем самым ее избежать.
            • 0
              Но откуда вообще взялась рекурсия?

              Вам привели уже три алгоритма, которые без всякого «засовывания рекурсии в данное» в простом цикле перебирают перестановки множества.
              • –3
                Рекурсия взялась из книги Липского, в ней описаны варианты генерации перестановок с рекурсией и без. Есть подобные описания и во многих других учебниках комбинаторики.
                Про три варианта алгоритма, мне кажется, вы слегка погорячились. Назвать алгоритмом несколько строк кода, которые надо запустить N! раз, я считаю не совсем корректным. Вы вполне можете привести полное описание своего алгоритма с «простым циклом» в отдельном сообщении.
                • 0
                  Скажите, а с каких пор алгоритмом можно называть только то, что занимает много строк кода?

                  PS Да кто такой этот Липский?!
                  • 0
                    Алгоритмом называется определенный порядок действий, который приводит к желанному результату.
                    Алгоритм может быть описан и на естественном языке, и блок схемой, и псевдокодом, способов много. ЯП один из способов реализации алгоритма. На разных ЯП ( и у разных программистов на одном языке) реализации будут отличаться, в том числе и количеством строк. Алгоритмы не сравнивают по количеству строк кода, это не имеет смысла. К сожалению, у меня не стоит компилятор Си, поэтому я не могу проверить то, что вы предлагаете.
                    • 0
                      Там записан алгоритм перехода от перестановки к следующей за ней в лексикографическом порядке. Суть: «Пусть в массиве числами от 1 до N записана перестановка. Найдем первый с конца элемента, который меньше следующего за ним. Затем в хвосте массива, следующем за найденным элементом, найдем минимальное число, большее чем этот элемент, переставим их местами и отсортируем хвост по возрастанию. Полученная перестановка и будет ответом.»
                      • 0
                        согласен, но это другой, широко описанный, в том числе Липским, алгоритм. Предложенный мной алгоритм работает по другому, именно поэтому я его и предложил. Наличие разных алгоритмов ведущих к одинаковому результату ( например сортировки ) никому не мешает.
                        • 0
                          Когда кто-то придумывает новый алгоритм, его всегда сравнивают со старыми по разным параметрам. И если такое сравнение не находит преимуществ (а вы в статье их не показали — да и сравнения не делалось) — то всегда следует вопрос: а зачем такой алгоритм вообще нужен?
                          • 0
                            В вашем первом посте приведен алгоритм получения одной перестановки из другой. В алгоритме получения всех перестановок множества это только часть задачи. В настоящее время существует несколько различных алгоритмов генерации всех перестановок. Они отличаются друг от друга, в том числе и по скорости выполнения.
                            По каким параметрам вы хотите сравнивать алгоритмы?
                            Вы готовы объяснить существование разных алгоритмов для решения одной той же задачи, сортировки например?
                            Задачу сравнительного анализа алгоритма я не ставил.
                            • +2
                              В вашем первом посте приведен алгоритм получения одной перестановки из другой. В алгоритме получения всех перестановок множества это только часть задачи.
                              Я считаю своих собеседников достаточно умными, чтобы самостоятельно превратить алгоритм получения следующей перестановки в алгоритм перечисления всех перестановок.
                              • –2
                                У вас подмена понятий, обсуждаем одно, вы предлагаете другое. Вы не предложили алгоритма получения всех перестановок, а писали о трех. То что вы предлагаете сделать самостоятельно можно сделать разными способами, именно поэтому я и предлагал вам создать новое сообщение и там все обсудить
                                • 0
                                  Я предложил алгоритм получения следующей перестановки. Этого достаточно для получения всех перестановок.

                                  Но, если вы настаиваете...
                                  int i;
                                  for (i=0; i<N; i++) array[i] = i+1;
                                  do {
                                      print_permutation(array);
                                  
                                      i = N - 2;
                                      while (i >= 0 && array[i] >= array[i+1]) i = i-1;
                                  
                                      if (i >= 0) {
                                          int j = i+1;
                                          while (array[i] < array[j+1]) j=j+1;
                                          int temp = array[i];
                                          array[i] = array[j];
                                          array[j] = temp;
                                      }
                                  
                                      for (int j = i+1, k = N-1; j < k; j=j+1, k=k-1) {
                                          int temp = array[j];
                                          array[j] = array[k];
                                          array[k] = temp;
                                      }
                                  
                                  } while (i >= 0);
                                  


                                  for (int L=0; ; L++) {
                                      int ind = L;
                                      for(int a=1;a<=N;a++){
                                           int k=ind%a;
                                           ind/=a;
                                           array[a-1]=array[k];
                                           array[k]=a;
                                      }
                                      print_permutation(array);
                                      if (ind > 0) break;
                                  }
                                  


                                  Ну а третий алгоритм в модификации не нуждается.
                                  • 0
                                    Я ни на чем не настаиваю. Мне непонятно, почему вы сразу не выложили этот коды ( из последнего топика).
                                    Они запустятся на ideone.com? ( print_permutation это некая процедура? ).
                                    Третий алгоритм вроде вовсе без вывода результата, но он действительно создаст все перестановки? ( которых N! )
                                    • 0
                                      А какой смысл генерировать все перестановки, если с ними потом ничего не делается? Предполагается, что пользователь подставит вместо вызова print_permutation нужную ему процедуру обработки. И, скорее всего, отдельные функции не запустятся — для запуска нужна программа, а не реализация алгоритма. Нужно задать N, завести массив, и для некоторых алгоритмов (а именно, для третьего) заполнить его значениями, перестановки которых надо выводить (в нём не предполагается, что это именно числа от 1 до N — могут быть любые значения).
                                      • 0
                                        Я согласен, сами по себе все перестановки никому не нужны. вместо writeln print и т.п. в реальных задачах ставятся определенные расчеты. но для того чтобы понять, все ли последовательности мы перебрали и желателен вывод, в Си разве нет вывода на консоль?.
                                        Предложенный в сообщении алгоритм выведет последовательность перестановок в лексикографическом порядке, если при первоначальном заполнении элементы массива тоже были в лексикографическом порядке. т.к. в получаемых перестановках н.б. часто меняется правый край, то вычисления в некоторых случаях можно упростить, не повторяя расчеты.
                                    • 0
                                      Во втором алгоритме надо либо начать с L=1, либо поставить if(ind>0) break; до печати перестановки. Иначе первая перестановка выведется дважды — в начале и в конце.
                        • 0
                          Вы сами себе противоречите.
                          Назвать алгоритмом несколько строк кода, которые надо запустить N! раз, я считаю не совсем корректным.
                          Алгоритмы не сравнивают по количеству строк кода, это не имеет смысла.

                          Алгоритм можно проверить тут: ideone.com/ (при условии, что вы хоть немного понимаете Cи/C++). К сожалению, я хотя и понимаю бейсик, но не настолько, чтобы на нем писать.

                          К слову, я намеренно избегал использования стандартной библиотеки языка, чтобы получившийся код был именно описанием алгоритма, а не демонстрацией возможностей стандартной библиотеки. Поэтому ваше заявление из первой цитаты довольно обидное.

                          А вот ваша программа, что под спойлером в конце статьи — именно что программа, а никак не описание алгоритма. В алгоритме получения перестановок множества не должно быть вызовов вида Лист1.Cells.Clear или MsgBox "stop calc"
                          • –2
                            С моей точки зрения описание алгоритма это одно ( текст, псевдокод, рисунки). Реализация на конкретном ЯП -это другое. Именно в силу различия синтаксиса.
                            В заметке я попытался описать алгоритм словами и рисунком. Возможно не очень удачно. Реализацию на VBA я вроде не называл описанием алгоритма. Это реализация, возможно и не самая лучшая, но я ее проверял и любой желающий может это также сделать при наличии Excel а и операций copy paste.
                            Какой именно код ( а не алгоритм) я должен проверять на ideone.com?
                            То что вы привели (в первом посте) код перехода от одной перестановки к другой прекрасно, недостаточно. Нужно это во что то обернуть.
                            То что вам не понравилось в реализации на VBA, это вывод результатов со спецификой Excel а.
                            Я не хотел вас обидеть, но продолжаю считать, что описание алгоритма и его реализация на ЯП разные вещи.
                            Я также не понял в чем я сам себе противоречу.
                            • 0
                              Алгоритм может быть описан и на естественном языке, и блок схемой, и псевдокодом, способов много.
              • +5
                Достаточно записать число в смешанной системе счисления — Первая цифра в двоичной системе счисления, вторая — в троичной, третья — в четверичной, и т.д. Это число будет представлять номер перестановки. Перестановка генерируется по следующему алгоритму: Читается число с самого старшего не нулевого разряда N — эта цифра будет означать с каким номером переставить N+1-ый элемент перестановки и так с каждым более младшим числом, пока не дойдём до первого. Так же легко переводится перестановка обратно в это число со смешанной системой счисления. А это число легко перевести в двоичную или десятичную и обратно. Т.е. по номеру перестановки можем легко её сгенерировать.
                • 0
                  Да, по номеру перестановка так и генерируется. Только вот работает эта радость за N2 — а потому для перебора всех перестановок лучше использовать тот алгоритм, который привел я.
                  • 0
                    Для конкретного номера она работает за O(N):
                      void Gen(int[] array,int N,int ind){
                          for(int a=1;a<=N;a++){
                             int k=ind%a;
                             ind/=a;
                             array[a-1]=array[ind];
                             array[ind]=a;
                         }
                      }
                    


                    array[a]=a+1;
                    • 0
                      Что-то я не понял, что этот алгоритм делает. Наверное, все же имелось в виду swap(array[a-1], array[k])?

                      Но тогда порядок перестановок — не лексикографический. Впрочем, признаю, порядка перестановок в этой задаче и не требовалось.
                      • 0
                        Алгоритм заполняет массив по мере роста индекса a. Периодически там выполняются пары присваиваний
                        array[a-1]=array[a-1]
                        array[a-1]=а
                        (т.е. сначала копируется неинициализированный элемент, а только потом инициализируется), но для целых чисел это не страшно.
                        Да, там опечатка — должно быть так:
                          void Gen(int[] array,int N,int ind){
                              for(int a=1;a<=N;a++){
                                 int k=ind%a;
                                 ind/=a;
                                 array[a-1]=array[k];
                                 array[k]=a;
                             }
                          }
                        

                        • 0
                          У вас еще и в объяснении опечатка получилась… Да, понял, красиво, хотя порядок перестановок и не определен.

                          Но алгоритм все равно получается медленнее при переборе всех перестановок, «мой» алгоритм выручает амортизированная стоимость.
                          • 0
                            Где опечатка в объяснении? По-моему, всё в порядке… Например, при N=3, k=4 присваивания будут такими:
                            array[0]=array[0]
                            array[0]=1
                            array[1]=array[0]
                            array[0]=2
                            array[2]=array[2]
                            array[2]=3
                            • 0
                              Алгоритм заполняет массив по мере роста индекса a. Периодически там выполняются пары присваиваний
                              array[a-1]=array[a-1]
                              array[a-1]=а
                              • 0
                                Да, это ровно то, что я хотел написать. В некоторых случаях (когда k==a-1), неинициализированный элемент копируется «вхолостую» — потому что не хочется писать лишний if.
                                • 0
                                  Если прочитать ваше сообщение как объяснение алгоритма, то получится, что только такие присваивания и делаются )
                • +1
                  Бейсик! Как это мило… Давненько тебя не видел, брат!
                  • –1
                    VBA конечно на любителя, но Excel есть практически у всех под Win. Конечно реализация на Си будет быстрее.
                  • 0
                    Если мы не ставим целью получить k-тую перестановку именно в лексикографическом порядке, — а просто k-ю перестановку в неповторяющейся последовательности перестановок (которых, конечно, n!), то можем пойти таким путём:

                    1. Вспомним алгоритм random_shuffle.
                    for(i=1; i<n; ++i)
                      swap( arr[i], arr[rand()%(i+1)] );
                    

                    2. Каждый набор чисел perm[n] = { 0..0, 0..1, 0..2, ..., 0..n-1 } уникально определяет перестановку n-элементного массива
                    3. Если номер k уже разложен в переменно-ричную систему счисления, то выполнить перестановку очень просто
                    for(i=1; i<n; ++i)
                      swap( arr[i], arr[perm[i]] );
                    

                    4. Разложим k в perm:
                    for(i=1; i<n; ++i)
                    {
                      perm[i] = k % (i+1);
                      k /= (i+1);
                    }
                    

                    5. Нам незачем хранить всё разложение, можем его прямо на лету получать.
                    for(i=1; i<n; ++i)
                    {
                      swap( arr[i], arr[k % (i+1)] );
                      k /= (i+1);
                    }
                    


                    Разумеется, мы не смотрим на содержимое переставляемого массива.
                    Если там есть дубликаты, то некоторые перестановки становятся эквивалентными.
                  • –1
                    У меня получилось три цикла, две проверки. И довольно затратная операция переворота. Почему-то думаю, её можно упростить. Но для php достаточно быстро. Алгоритм, вероятно, не потягается с тем, что здесь уже привели и требует отсортированного массива в обратном порядке. Но вывод вполне отражённый лексикографический. :) Зато, думаю, довольно прозрачно получилось.
                    $a='876543210';
                    $b=strrev($a);
                    $n=strlen($a);
                    while ($a !=$b) {
                    
                    for($i=0; $i < $n; $i++) {
                    
                    if ($a[$i] < $a[$i-1]) {
                    
                    for($j=0; $j < $n; $j++) {
                    
                    if ($a[$j] > $a[$i]) {
                    
                    $c=$a[$j];
                    $a[$j]=$a[$i];
                    $a[$i]=$c;
                    
                    $x=strrev(substr($a, 0, $i));
                    $y=substr($a, $i);
                    print $a=$x.$y;
                    print ‘<br/>’;
                    break 2;
                    }
                    }
                    }
                    }
                    
                    }
                    

                    https://dcc0blog.wordpress.com/2016/01/19/%D0%BF%D0%B5%D1%80%D0%B5%D1%81%D1%82%D0%B0%D0%BD%D0%BE%D0%B2%D0%BA%D0%B8-php/ — ссылка на описание
                    • –1
                      Жаль, все-таки, что нет описания алгоритма в виде: шаг 1, шаг 2, с кратким описанием данных шагов.
                      Видимо, самое трудное в алгоритмах — это их описание.
                      • 0
                        Мне казалось, что алгоритм понятен из набора картинок, приведенных в тексте. В VBA коде мне кажется все достаточно понятно. Попробую словами.
                        1 этап
                        формируем матрицу N на N ( нужна левая верхняя половина )
                        первая строка числа по порядку 1,2..N
                        Для каждой строки матрицы храним указатель на колонку ( исключаемую для нижних рядов)
                        в начале он = 1 по всем строкам
                        получаем следующие строки ( уменьшается число колонок)
                        1,2… N
                        2,3… N
                        3,4… N
                        процесс заполнения матрицы останавливается, когда остаются
                        N-1,N. ( хвостик ) Строчек в матрице N-1.
                        Первый результат получен — это вертикальный столбец от 1 до (N-2)
                        из столбцов на которые указывают указатели ( построчные ).
                        + пара N-1,N
                        N ,N-1
                        2 этап
                        Увеличиваем указатели, начиная снизу,
                        в строке матрицы (N-2) увеличиваем указатель на 1
                        в строку (N-1) заносим числа из Строки (N-2)
                        получаем результат, как в первом этапе

                        Если меняем указатель на каком то уровне, при этом все указатели ниже
                        сбрасываем в 1,

                        Если указатель на уровне X увеличивать далее некуда,
                        переходим на уровень выше и меняем его там.

                        Процесс заканчивается когда
                        на самом верхнем уровне увеличивать указатель далее некуда

                        Строка на уровне X+ 1формируется = строке на уровне X без элемента на который указывает указатель строки X
                        Мне кажется если присмотреться к картинкам, то мой текст станет понятнее

                        • 0
                          Спасибо. Только не подумайте, что я к чему-то придираюсь. Может, это конкретно в моём восприятии описание алгоритма — это набор шагов, где за каждым действием стоит такое описание, что оно:
                          1) Не вызывает двусмысленности.
                          2) Описание шага однозначно соответствует действию.
                          3) В описании нет дополнительной информации.

                          Вот пример, Вы начинает со слов: «формируем матрицу».
                          Как мне понять, что за этим стоит — пустой массив, для которого Вы сразу определяете и его длину?
                          Или уже есть готовый входной алфавит длины n?

                      • 0
                        Вы пожалуйста определитесь, что вы хотите
                        описание алгоритма — в нем нет подробностей реализации, реализовывать можно на любом языке
                        или реализацию на конкретном языке.
                        во втором случае посмотрите код на VBA
                        для первого случая предложение ->формируем матрицу N на N < — очевидно — это двумерный массив

                        • 0
                          Спасибо за ответ. К сожалению, не знаю VBA.

                          Сейчас посидел еще немного над алгоритмом Нарайяны и вдруг осенило, что обе проверки можно выбросить.
                          А также убрать break вообще и получилось так — один внешний цикл, два вложенных, не друг в друга — один определяет позицию, второй находит «ближайшее большее», обмен и оборот хвоста с помощью substr.
                          Тоже самое и на c++ получилось закодировать. Получился лексикографический порядок, только слева напарво.

                          $b=«12345»;
                          $a=strrev($b);

                          while ($a !=$b) {
                          $i=0;
                          while($a[$i] > $a[$i-1]) {
                          $i++;
                          }

                          $j=0;
                          while($a[$j] < $a[$i]) {
                          $j++;
                          }

                          $c=$a[$j];
                          $a[$j]=$a[$i];
                          $a[$i]=$c;

                          $x=strrev(substr($a, 0, $i));
                          $y=substr($a, $i);

                          print $a=$x.$y;
                          print 'br';

                          }

                        Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.