Получение перестановки по номеру

Pahan

Дык это же классическая задача теории вероятностей (комбинаторики). Возьми первый томик Феллера и поищи слово "серии". Про серии много чего известно.

 

2 Black_mirror:
В основном цикле:

Код (Text):

1. for(int i=0;i<N;i++)
2.     alter[i]=mark;

и ниже:

Код (Text):

1. alter[i]=alter[next[i]];

Нет ли здесь опечатки?

2 crypto:
На самом деле предложенный алгоритм кажется мне уже достаточно хорошим и убыстрять я его планировал именно засчет тонкостей реализации.
Но Феллера посмотрю, спасибо. Думаю там все равно будет много полезного.

 

Pahan
Подаётся ей массив бит и его длина, ну а функция печатает все различные цепочки длиной от 1 до N. В массиве next хранятся указатели на следующую такую же цепочку. А массив alter нужен только для разделения списка на два при удлинении цепочек на один бит. Если нужно выводить количество одинаковых цепочек, по можно перед выводом добавить пару циклов и перед переводом строки выводить alter:

Код (Text):

1. for(int i=0;i<=N-len;i++)
2.   alter[i]=1;
3. for(int i=0;i<=N-len;i++)
4.   alter[next[i]]+=alter[i];

Ну а если нужно в отсортированном виде выводить, то придётся делать массив указателей на элементы для которых next>=mark и сортировать его.

 

Pahan

Здесь нет, но вообще я этот код в браузере писал, так что могут быть другие баги баги.

 

2 Black_mirror
еще одну опечатку при выводе на

Код (Text):

1.  int j=j

я исправил. Код запустил, все работает.
Можно узнать общую идею алгоритма, а то по коду не могу ее уловить? Хочу сравнить по трудоемкости с той, которую я использую и по возможности переделать для случая когда алфавит больше, чем двоичный.

 

*

Код (Text):

1. int j=i

 

Pahan
Сложность алгоритма N*N. А общая идея такова, что сначала все биты связываются в список цепочек нулевой длины, а потом увеличиваем длину цепочки на один бит и расщепляем каждый список на два: список элементов, которые оканчиваются на 1, и список элементов, которые оканчиваются на 0. Ну а в alter хранится указатель на следующий элемент списка с элементами отличающимися от текущего в последнем бите. Если число символов в алфавите не большое, то можно конечно добавить к массиву alter еще одну размерность, но это приведёт к появлению мультипликативной констранты, равной числу символов в алфавите. Если кто знает как более эффективно расщеплять списки, пусть поделится.

 

Black_mirror
По моим представлениям, алгоритм предложенный Y_Mur в этой теме обладает трудоемкостью не хуже, чем N*N.

 

Pahan
Ну это и есть его алгоритм

 

глупости. что значит под юникс? там исходники выложены, что мешает их собрать?

 

luckysundog
Уже ничего=) Собрал ее через cygwin - работает.