Pull to refresh

Comments 49

Один вопрос: зачем так сложно? Зачем вообще список?

Не знаю, что там было написано у Липского — но за три простых цикла находится следующая перестановка. Осталось запустить этот алгоритм 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 (иначе алгоритм до нашей смерти не закончит работу), поэтому если уж так хочется сравнивать по памяти алгоритмы, то разумнее уж прямо в байтах написать, сколько кому требуется, а не асимптотики сравнивать.
Нет, возможно:

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! раз, я считаю не совсем корректным. Вы вполне можете привести полное описание своего алгоритма с «простым циклом» в отдельном сообщении.
Скажите, а с каких пор алгоритмом можно называть только то, что занимает много строк кода?

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

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

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

А вот ваша программа, что под спойлером в конце статьи — именно что программа, а никак не описание алгоритма. В алгоритме получения перестановок множества не должно быть вызовов вида Лист1.Cells.Clear или MsgBox "stop calc"
С моей точки зрения описание алгоритма это одно ( текст, псевдокод, рисунки). Реализация на конкретном ЯП -это другое. Именно в силу различия синтаксиса.
В заметке я попытался описать алгоритм словами и рисунком. Возможно не очень удачно. Реализацию на VBA я вроде не называл описанием алгоритма. Это реализация, возможно и не самая лучшая, но я ее проверял и любой желающий может это также сделать при наличии Excel а и операций copy paste.
Какой именно код ( а не алгоритм) я должен проверять на ideone.com?
То что вы привели (в первом посте) код перехода от одной перестановки к другой прекрасно, недостаточно. Нужно это во что то обернуть.
То что вам не понравилось в реализации на VBA, это вывод результатов со спецификой Excel а.
Я не хотел вас обидеть, но продолжаю считать, что описание алгоритма и его реализация на ЯП разные вещи.
Я также не понял в чем я сам себе противоречу.
Алгоритм может быть описан и на естественном языке, и блок схемой, и псевдокодом, способов много.
Достаточно записать число в смешанной системе счисления — Первая цифра в двоичной системе счисления, вторая — в троичной, третья — в четверичной, и т.д. Это число будет представлять номер перестановки. Перестановка генерируется по следующему алгоритму: Читается число с самого старшего не нулевого разряда N — эта цифра будет означать с каким номером переставить N+1-ый элемент перестановки и так с каждым более младшим числом, пока не дойдём до первого. Так же легко переводится перестановка обратно в это число со смешанной системой счисления. А это число легко перевести в двоичную или десятичную и обратно. Т.е. по номеру перестановки можем легко её сгенерировать.
Да, по номеру перестановка так и генерируется. Только вот работает эта радость за N2 — а потому для перебора всех перестановок лучше использовать тот алгоритм, который привел я.
Для конкретного номера она работает за 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;
Что-то я не понял, что этот алгоритм делает. Наверное, все же имелось в виду swap(array[a-1], array[k])?

Но тогда порядок перестановок — не лексикографический. Впрочем, признаю, порядка перестановок в этой задаче и не требовалось.
Алгоритм заполняет массив по мере роста индекса 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;
     }
  }

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

Но алгоритм все равно получается медленнее при переборе всех перестановок, «мой» алгоритм выручает амортизированная стоимость.
Где опечатка в объяснении? По-моему, всё в порядке… Например, при 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
Алгоритм заполняет массив по мере роста индекса a. Периодически там выполняются пары присваиваний
array[a-1]=array[a-1]
array[a-1]=а
Да, это ровно то, что я хотел написать. В некоторых случаях (когда k==a-1), неинициализированный элемент копируется «вхолостую» — потому что не хочется писать лишний if.
Если прочитать ваше сообщение как объяснение алгоритма, то получится, что только такие присваивания и делаются )
Бейсик! Как это мило… Давненько тебя не видел, брат!
VBA конечно на любителя, но Excel есть практически у всех под Win. Конечно реализация на Си будет быстрее.
Если мы не ставим целью получить 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);
}


Разумеется, мы не смотрим на содержимое переставляемого массива.
Если там есть дубликаты, то некоторые перестановки становятся эквивалентными.
У меня получилось три цикла, две проверки. И довольно затратная операция переворота. Почему-то думаю, её можно упростить. Но для 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) Не вызывает двусмысленности.
2) Описание шага однозначно соответствует действию.
3) В описании нет дополнительной информации.

Вот пример, Вы начинает со слов: «формируем матрицу».
Как мне понять, что за этим стоит — пустой массив, для которого Вы сразу определяете и его длину?
Или уже есть готовый входной алфавит длины 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';

}
Only those users with full accounts are able to leave comments. Log in, please.