Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 49
Один вопрос: зачем так сложно? Зачем вообще список?
Не знаю, что там было написано у Липского — но за три простых цикла находится следующая перестановка. Осталось запустить этот алгоритм N! раз — и мы нашли все перестановки.
PS код не запускал, он может содержать опечатки.
Не знаю, что там было написано у Липского — но за три простых цикла находится следующая перестановка. Осталось запустить этот алгоритм 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 код не запускал, он может содержать опечатки.
Нехорошо, что здесь используется сравнение элементов array. В общем случае, мы ищем перестановки произвольного множества, а на них порядка может и не быть.
В общем случае array — это массив индексов.
Значит, приходится тратить место на лишний массив. А вы попробуйте перебрать перестановки в одном массиве, без рекурсии, за O(1) дополнительной памяти и желательно, за O(N!) операций :) (за O((N+1)!) делается с помощью алгоритма из комментария ниже). Не уверен, впрочем, что это возможно…
Для номера текущей перестановки требуется отвести Θ(N log N) памяти — т.е. мой алгоритм просит даже меньше.
Действительно. Если хранить индексы в битовом массиве, реализованном на одной или двух целых переменных, то памяти будет примерно столько же.
Упс… именно что столько же. Я допустил ту же самую ошибку, которую нашел в ваших рассуждениях )
Это скорее вопрос формализации задачи. Если всё честно считать в битах, то да, Θ(N log N) и там, и там. Более того, очевидно, что, если в основном массиве непонятно что записано и мы только меняем местами его элементы, это нижняя граница по дополнительной памяти (потому что всю информацию мы берем только из дополнительной памяти, значит перед началом генерации каждой перестановки в этой памяти должно быть записано своё уникальное значение, последовательностей N!, значит нам требует не меньше log2 N! бит).
Но по факту, N ограничено сверху очень маленькой константой порядка 20 (иначе алгоритм до нашей смерти не закончит работу), поэтому если уж так хочется сравнивать по памяти алгоритмы, то разумнее уж прямо в байтах написать, сколько кому требуется, а не асимптотики сравнивать.
Но по факту, N ограничено сверху очень маленькой константой порядка 20 (иначе алгоритм до нашей смерти не закончит работу), поэтому если уж так хочется сравнивать по памяти алгоритмы, то разумнее уж прямо в байтах написать, сколько кому требуется, а не асимптотики сравнивать.
Нет, возможно:
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;
}
}
Да, я тоже думал в эту сторону, но остановился на понимании того, что переменная ind в любом случае займет Θ(N log N) памяти асимптотически. А lemelisk даже объяснил, почему это ограничение никак не обойти.
Я немного извиняюсь, но в моем контексте список это тоже массив. Сложности в алгоритме не вижу, рисунок, как мне кажется, достаточно нагляден. Я рассматриваю алгоритм как попытку рекурсию «засунуть» в данные и тем самым ее избежать.
Но откуда вообще взялась рекурсия?
Вам привели уже три алгоритма, которые без всякого «засовывания рекурсии в данное» в простом цикле перебирают перестановки множества.
Вам привели уже три алгоритма, которые без всякого «засовывания рекурсии в данное» в простом цикле перебирают перестановки множества.
Рекурсия взялась из книги Липского, в ней описаны варианты генерации перестановок с рекурсией и без. Есть подобные описания и во многих других учебниках комбинаторики.
Про три варианта алгоритма, мне кажется, вы слегка погорячились. Назвать алгоритмом несколько строк кода, которые надо запустить N! раз, я считаю не совсем корректным. Вы вполне можете привести полное описание своего алгоритма с «простым циклом» в отдельном сообщении.
Про три варианта алгоритма, мне кажется, вы слегка погорячились. Назвать алгоритмом несколько строк кода, которые надо запустить N! раз, я считаю не совсем корректным. Вы вполне можете привести полное описание своего алгоритма с «простым циклом» в отдельном сообщении.
Скажите, а с каких пор алгоритмом можно называть только то, что занимает много строк кода?
PS Да кто такой этот Липский?!
PS Да кто такой этот Липский?!
Алгоритмом называется определенный порядок действий, который приводит к желанному результату.
Алгоритм может быть описан и на естественном языке, и блок схемой, и псевдокодом, способов много. ЯП один из способов реализации алгоритма. На разных ЯП ( и у разных программистов на одном языке) реализации будут отличаться, в том числе и количеством строк. Алгоритмы не сравнивают по количеству строк кода, это не имеет смысла. К сожалению, у меня не стоит компилятор Си, поэтому я не могу проверить то, что вы предлагаете.
Алгоритм может быть описан и на естественном языке, и блок схемой, и псевдокодом, способов много. ЯП один из способов реализации алгоритма. На разных ЯП ( и у разных программистов на одном языке) реализации будут отличаться, в том числе и количеством строк. Алгоритмы не сравнивают по количеству строк кода, это не имеет смысла. К сожалению, у меня не стоит компилятор Си, поэтому я не могу проверить то, что вы предлагаете.
Там записан алгоритм перехода от перестановки к следующей за ней в лексикографическом порядке. Суть: «Пусть в массиве числами от 1 до N записана перестановка. Найдем первый с конца элемента, который меньше следующего за ним. Затем в хвосте массива, следующем за найденным элементом, найдем минимальное число, большее чем этот элемент, переставим их местами и отсортируем хвост по возрастанию. Полученная перестановка и будет ответом.»
согласен, но это другой, широко описанный, в том числе Липским, алгоритм. Предложенный мной алгоритм работает по другому, именно поэтому я его и предложил. Наличие разных алгоритмов ведущих к одинаковому результату ( например сортировки ) никому не мешает.
Когда кто-то придумывает новый алгоритм, его всегда сравнивают со старыми по разным параметрам. И если такое сравнение не находит преимуществ (а вы в статье их не показали — да и сравнения не делалось) — то всегда следует вопрос: а зачем такой алгоритм вообще нужен?
В вашем первом посте приведен алгоритм получения одной перестановки из другой. В алгоритме получения всех перестановок множества это только часть задачи. В настоящее время существует несколько различных алгоритмов генерации всех перестановок. Они отличаются друг от друга, в том числе и по скорости выполнения.
По каким параметрам вы хотите сравнивать алгоритмы?
Вы готовы объяснить существование разных алгоритмов для решения одной той же задачи, сортировки например?
Задачу сравнительного анализа алгоритма я не ставил.
По каким параметрам вы хотите сравнивать алгоритмы?
Вы готовы объяснить существование разных алгоритмов для решения одной той же задачи, сортировки например?
Задачу сравнительного анализа алгоритма я не ставил.
В вашем первом посте приведен алгоритм получения одной перестановки из другой. В алгоритме получения всех перестановок множества это только часть задачи.Я считаю своих собеседников достаточно умными, чтобы самостоятельно превратить алгоритм получения следующей перестановки в алгоритм перечисления всех перестановок.
У вас подмена понятий, обсуждаем одно, вы предлагаете другое. Вы не предложили алгоритма получения всех перестановок, а писали о трех. То что вы предлагаете сделать самостоятельно можно сделать разными способами, именно поэтому я и предлагал вам создать новое сообщение и там все обсудить
Я предложил алгоритм получения следующей перестановки. Этого достаточно для получения всех перестановок.
Но, если вы настаиваете...
Ну а третий алгоритм в модификации не нуждается.
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;
}
Ну а третий алгоритм в модификации не нуждается.
Я ни на чем не настаиваю. Мне непонятно, почему вы сразу не выложили этот коды ( из последнего топика).
Они запустятся на ideone.com? ( print_permutation это некая процедура? ).
Третий алгоритм вроде вовсе без вывода результата, но он действительно создаст все перестановки? ( которых N! )
Они запустятся на ideone.com? ( print_permutation это некая процедура? ).
Третий алгоритм вроде вовсе без вывода результата, но он действительно создаст все перестановки? ( которых N! )
А какой смысл генерировать все перестановки, если с ними потом ничего не делается? Предполагается, что пользователь подставит вместо вызова print_permutation нужную ему процедуру обработки. И, скорее всего, отдельные функции не запустятся — для запуска нужна программа, а не реализация алгоритма. Нужно задать N, завести массив, и для некоторых алгоритмов (а именно, для третьего) заполнить его значениями, перестановки которых надо выводить (в нём не предполагается, что это именно числа от 1 до N — могут быть любые значения).
Я согласен, сами по себе все перестановки никому не нужны. вместо writeln print и т.п. в реальных задачах ставятся определенные расчеты. но для того чтобы понять, все ли последовательности мы перебрали и желателен вывод, в Си разве нет вывода на консоль?.
Предложенный в сообщении алгоритм выведет последовательность перестановок в лексикографическом порядке, если при первоначальном заполнении элементы массива тоже были в лексикографическом порядке. т.к. в получаемых перестановках н.б. часто меняется правый край, то вычисления в некоторых случаях можно упростить, не повторяя расчеты.
Предложенный в сообщении алгоритм выведет последовательность перестановок в лексикографическом порядке, если при первоначальном заполнении элементы массива тоже были в лексикографическом порядке. т.к. в получаемых перестановках н.б. часто меняется правый край, то вычисления в некоторых случаях можно упростить, не повторяя расчеты.
Во втором алгоритме надо либо начать с L=1, либо поставить if(ind>0) break; до печати перестановки. Иначе первая перестановка выведется дважды — в начале и в конце.
Вы сами себе противоречите.
Алгоритм можно проверить тут: ideone.com/ (при условии, что вы хоть немного понимаете Cи/C++). К сожалению, я хотя и понимаю бейсик, но не настолько, чтобы на нем писать.
К слову, я намеренно избегал использования стандартной библиотеки языка, чтобы получившийся код был именно описанием алгоритма, а не демонстрацией возможностей стандартной библиотеки. Поэтому ваше заявление из первой цитаты довольно обидное.
А вот ваша программа, что под спойлером в конце статьи — именно что программа, а никак не описание алгоритма. В алгоритме получения перестановок множества не должно быть вызовов вида
Назвать алгоритмом несколько строк кода, которые надо запустить N! раз, я считаю не совсем корректным.
Алгоритмы не сравнивают по количеству строк кода, это не имеет смысла.
Алгоритм можно проверить тут: ideone.com/ (при условии, что вы хоть немного понимаете Cи/C++). К сожалению, я хотя и понимаю бейсик, но не настолько, чтобы на нем писать.
К слову, я намеренно избегал использования стандартной библиотеки языка, чтобы получившийся код был именно описанием алгоритма, а не демонстрацией возможностей стандартной библиотеки. Поэтому ваше заявление из первой цитаты довольно обидное.
А вот ваша программа, что под спойлером в конце статьи — именно что программа, а никак не описание алгоритма. В алгоритме получения перестановок множества не должно быть вызовов вида
Лист1.Cells.Clear или MsgBox "stop calc"С моей точки зрения описание алгоритма это одно ( текст, псевдокод, рисунки). Реализация на конкретном ЯП -это другое. Именно в силу различия синтаксиса.
В заметке я попытался описать алгоритм словами и рисунком. Возможно не очень удачно. Реализацию на VBA я вроде не называл описанием алгоритма. Это реализация, возможно и не самая лучшая, но я ее проверял и любой желающий может это также сделать при наличии Excel а и операций copy paste.
Какой именно код ( а не алгоритм) я должен проверять на ideone.com?
То что вы привели (в первом посте) код перехода от одной перестановки к другой прекрасно, недостаточно. Нужно это во что то обернуть.
То что вам не понравилось в реализации на VBA, это вывод результатов со спецификой Excel а.
Я не хотел вас обидеть, но продолжаю считать, что описание алгоритма и его реализация на ЯП разные вещи.
Я также не понял в чем я сам себе противоречу.
В заметке я попытался описать алгоритм словами и рисунком. Возможно не очень удачно. Реализацию на VBA я вроде не называл описанием алгоритма. Это реализация, возможно и не самая лучшая, но я ее проверял и любой желающий может это также сделать при наличии Excel а и операций copy paste.
Какой именно код ( а не алгоритм) я должен проверять на ideone.com?
То что вы привели (в первом посте) код перехода от одной перестановки к другой прекрасно, недостаточно. Нужно это во что то обернуть.
То что вам не понравилось в реализации на VBA, это вывод результатов со спецификой Excel а.
Я не хотел вас обидеть, но продолжаю считать, что описание алгоритма и его реализация на ЯП разные вещи.
Я также не понял в чем я сам себе противоречу.
Достаточно записать число в смешанной системе счисления — Первая цифра в двоичной системе счисления, вторая — в троичной, третья — в четверичной, и т.д. Это число будет представлять номер перестановки. Перестановка генерируется по следующему алгоритму: Читается число с самого старшего не нулевого разряда N — эта цифра будет означать с каким номером переставить N+1-ый элемент перестановки и так с каждым более младшим числом, пока не дойдём до первого. Так же легко переводится перестановка обратно в это число со смешанной системой счисления. А это число легко перевести в двоичную или десятичную и обратно. Т.е. по номеру перестановки можем легко её сгенерировать.
Да, по номеру перестановка так и генерируется. Только вот работает эта радость за N2 — а потому для перебора всех перестановок лучше использовать тот алгоритм, который привел я.
Для конкретного номера она работает за O(N):
array[a]=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[ind];
array[ind]=a;
}
}
array[a]=a+1;
Что-то я не понял, что этот алгоритм делает. Наверное, все же имелось в виду
Но тогда порядок перестановок — не лексикографический. Впрочем, признаю, порядка перестановок в этой задаче и не требовалось.
swap(array[a-1], array[k])?Но тогда порядок перестановок — не лексикографический. Впрочем, признаю, порядка перестановок в этой задаче и не требовалось.
Алгоритм заполняет массив по мере роста индекса a. Периодически там выполняются пары присваиваний
array[a-1]=array[a-1]
array[a-1]=а
(т.е. сначала копируется неинициализированный элемент, а только потом инициализируется), но для целых чисел это не страшно.
Да, там опечатка — должно быть так:
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;
}
}
У вас еще и в объяснении опечатка получилась… Да, понял, красиво, хотя порядок перестановок и не определен.
Но алгоритм все равно получается медленнее при переборе всех перестановок, «мой» алгоритм выручает амортизированная стоимость.
Но алгоритм все равно получается медленнее при переборе всех перестановок, «мой» алгоритм выручает амортизированная стоимость.
Где опечатка в объяснении? По-моему, всё в порядке… Например, при 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
array[0]=array[0]
array[0]=1
array[1]=array[0]
array[0]=2
array[2]=array[2]
array[2]=3
Бейсик! Как это мило… Давненько тебя не видел, брат!
Если мы не ставим целью получить k-тую перестановку именно в лексикографическом порядке, — а просто k-ю перестановку в неповторяющейся последовательности перестановок (которых, конечно, n!), то можем пойти таким путём:
1. Вспомним алгоритм random_shuffle.
2. Каждый набор чисел perm[n] = { 0..0, 0..1, 0..2, ..., 0..n-1 } уникально определяет перестановку n-элементного массива
3. Если номер k уже разложен в переменно-ричную систему счисления, то выполнить перестановку очень просто
4. Разложим k в perm:
5. Нам незачем хранить всё разложение, можем его прямо на лету получать.
Разумеется, мы не смотрим на содержимое переставляемого массива.
Если там есть дубликаты, то некоторые перестановки становятся эквивалентными.
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);
}
Разумеется, мы не смотрим на содержимое переставляемого массива.
Если там есть дубликаты, то некоторые перестановки становятся эквивалентными.
Комментарии не читай, сразу пиши свой?
Вот описание того же самого алгоритма, что привели вы: habrahabr.ru/post/248493/#comment_8242301
А вот и его реализация (с допущением, что исходное множество — 1..N): habrahabr.ru/post/248493/#comment_8242367
Вот описание того же самого алгоритма, что привели вы: habrahabr.ru/post/248493/#comment_8242301
А вот и его реализация (с допущением, что исходное множество — 1..N): habrahabr.ru/post/248493/#comment_8242367
У меня получилось три цикла, две проверки. И довольно затратная операция переворота. Почему-то думаю, её можно упростить. Но для php достаточно быстро. Алгоритм, вероятно, не потягается с тем, что здесь уже привели и требует отсортированного массива в обратном порядке. Но вывод вполне отражённый лексикографический. :) Зато, думаю, довольно прозрачно получилось.
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/ — ссылка на описание
$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, шаг 2, с кратким описанием данных шагов.
Видимо, самое трудное в алгоритмах — это их описание.
Видимо, самое трудное в алгоритмах — это их описание.
Мне казалось, что алгоритм понятен из набора картинок, приведенных в тексте. В 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
Мне кажется если присмотреться к картинкам, то мой текст станет понятнее
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
Мне кажется если присмотреться к картинкам, то мой текст станет понятнее
Спасибо. Только не подумайте, что я к чему-то придираюсь. Может, это конкретно в моём восприятии описание алгоритма — это набор шагов, где за каждым действием стоит такое описание, что оно:
1) Не вызывает двусмысленности.
2) Описание шага однозначно соответствует действию.
3) В описании нет дополнительной информации.
Вот пример, Вы начинает со слов: «формируем матрицу».
Как мне понять, что за этим стоит — пустой массив, для которого Вы сразу определяете и его длину?
Или уже есть готовый входной алфавит длины n?
1) Не вызывает двусмысленности.
2) Описание шага однозначно соответствует действию.
3) В описании нет дополнительной информации.
Вот пример, Вы начинает со слов: «формируем матрицу».
Как мне понять, что за этим стоит — пустой массив, для которого Вы сразу определяете и его длину?
Или уже есть готовый входной алфавит длины n?
Вы пожалуйста определитесь, что вы хотите
описание алгоритма — в нем нет подробностей реализации, реализовывать можно на любом языке
или реализацию на конкретном языке.
во втором случае посмотрите код на VBA
для первого случая предложение ->формируем матрицу N на N < — очевидно — это двумерный массив
описание алгоритма — в нем нет подробностей реализации, реализовывать можно на любом языке
или реализацию на конкретном языке.
во втором случае посмотрите код на VBA
для первого случая предложение ->формируем матрицу N на N < — очевидно — это двумерный массив
Спасибо за ответ. К сожалению, не знаю 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';
}
Сейчас посидел еще немного над алгоритмом Нарайяны и вдруг осенило, что обе проверки можно выбросить.
А также убрать 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';
}
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Нерекурсивный алгоритм генерации перестановок