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

Я уже писал этот вопрос в теме про случайные перестановки, но она старая и боюсь туда никто не заглянет, поэтому создал новую.
подскажите, пожалуйста, как решить проблему, когда по номеру нужно получить перестановку элементов 0, 1 длины n например.
Т.е. если n=3, перестановки
000
001
...
111
то по номеру 2 нужно получить 001? Подскажите плиз.

 

Во-первых, это не перестановки. Но судя по твоему примеру, нужно просто перевести номер перестановки ( начиная с 0 ) в двоичную систему счисления.

 

в примере не перестановка, Forever правильно все сказал... по научному это можно назвать множеством всех подстановок длины n над множеством {0, 1}, что эквивалентно отрезку последовательных двоичных чисел... если все же нужно работать с перестановками, то можешь воспользоваться следующим алгоритмом:
http://algolist.ru/maths/combinat/permutations.php
он "немного" неоптимален, так как чтобы получить m-тую перестановку, придется сделать m-1 перестановок... но другого пути, я чет не вижу...

 

Rel
http://en.wikipedia.org/wiki/Permutation -- здесь очень хороший алгоритм.

 

А как получить перестановку по номеру если известно количество нулей и количество единиц в перестановке?

Т.е для 3 нулей и 2 единиц
0) 00011
1) 00101
2) 00110
3) 01001
4) 01010
5) 01100
6) 10001
7) 10010
8) 10100
9) 11000

 

.

 

пуффф... вот ты переставляешь элементы последовательности по определенному алгоритму... что мешает тебе выполнить этот алгоритм n итераций, чтобы получить n-тую перестановку? чет мне кажется, что ты не найдешь такой "формулы", которой можно получить n-ую перестановку... даж в трижды проклятой математике композиция нескольких перестановок выполняется последовательной композицией подстановок... то бишь:
1: (12345)
2: (12345) * (12345) = (23451)
3: (12345) * (12345) * (12345) = (23451) * (12345) = (34512)
этот пример (очень простой) для множества S = {1, 2, 3, 4, 5}, начальный элемент e = (12345), операция сдвига влево (собсна композиция подстановки на саму себя)... и такая система кстати будет образовывать циклическую группу из 5 элементов... муахахаха (коварный смех)

Mika0x65, в твоей статье два алгоритма... один из них лексикографический - абсолютно такой же, как в моей статье... то есть он генерирует последовательность перестановок начиная с (12345), заканчивая (54321)... а второй он лучше тем, что быстрее, но к сожалению не предоставляет отсортированную последовательность... вот в чем вся соль...

но западло в том, что оба эти алгоритма созданы, чтобы генерировать последовательности перестановок для случая, когда количество элементов во множестве равно длине перестановки... то есть для случая автора темы будут появляться повторы... на конкретном примере, он правильно переставил элементы, и получилось всего 9 членов в последовательности, но по нашим алгоритмам их получилось бы 5!... это 120 вроде бы...

балин, чет я разумничался... извиняйте...

 

Не 5!, а C из n по k.

 

Спасибо за внимание к проблеме.
2 Forever и Rel.

Да,видимо называть это переставновкам некорректно. Иначе говоря, я имел ввиду все возможные цепочки длины n алфавита {0,1}. Помоему варинат, что просто брать номер перестановки и переводить его в двоичную систему - это выход. Однако у меня n порядка 1000. т.е последняя перестановка будет номер 2^1000 (около 300 знаков) и переводить такое число в двоичную систему проблемно. Нужна видимо длинная арфметика?
Подскажите плиз ссылку на пакет типа freelip только для винды. или описание на него.

 

Если перестановок не много можно организовать выборку из таблицы.

 

я помню сам реализовывал длинную арифметику, когда в институте учился... поспорил с преподом, что вычислю 1000ый член последовательности фибоначчи... если нужно там несколько всего операция простых, типа сложения или поразрядного сдвига, то можно самому написать... про готовые решения я не в теме к сожалению, не приходилось сталкиваться((((

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

 

Можно сделат проще, чем длинная арифметика и последовательная генерация. Причем намного.
Вот смотри. Пусть n - количество 0 и 1, m - количество 1.
Общее количество таких расстановок будет C(n, m). Заметим, что в начале будут идти расстановки в которых на самой первой позиции (слева направо) стоит 0. Таких расстановок будет C(n - 1, m). А потом те, в которых стоит на первом месте 1, их будет C(n - 1, m - 1).
Алгоритм прост :
0. Пусть k - номер генерируемой перестановки, начиная с 1.
1. При заданных n и m, смотрим что больше C(n - 1, m) или k.
1.1. Если k <= C(n - 1, m), то напервом месте стоит 0. Полагаем n = n - 1.
Переходим к пункту 1.
1.2. Иначе на первом месте стоит 1. Полагаем k = k - C(n - 1, m), n = n - 1, m = m - 1.
Переходим к пункту 1.

 

А собственно откуда берётся этот номер в твоей программе? - ты что вручную эти 300 цифр набираешь и хранишь в виде ascii строки? А если этот номер как-то вычисляется, то он уже в двоичной системе )

 

Скорей всего автор таким образом "архивирует" файл с результатами работы программы (вместо 300 байт хранит 1).

 

задача криптографическая. сейчас работаю над усовершенствованием алгоритма, но без пакета не обойтись похоже даже при оптимизации. хотя бы для того чтобы посчитать 2 в 100-ой например. А пакет, а не самописаная функция, т.к. думаю, что пакетная ф-ция будет работать быстрее.

 

Алгоритм, описанный мною выше, подошел или нет?

 

Forever
k = k - C(n - 1, m) где n~1000, а k соответсвенно 1000-битное число это тоже длинная арифметика , причём для того чтобы сделать k = k - ... очень желательно перевести k в родной для процессора двоичный формат, что собственно уже является решением задачи )

 

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

 

судя по примеру в #1 для этого необходимо и достаточно вычесть 1 из двоичного представления порядкового номера (k) этой самой перестановки и в #9 ТС подтвердил, что это решение ему и нужно

 

[del]