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

Тема в разделе "WASM.A&O", создана пользователем Pahan, 10 янв 2009.

  1. Pahan

    Pahan New Member

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

    Forever Виталий

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

    Rel Well-Known Member

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

    Mika0x65 New Member

    Публикаций:
    0
    Rel
    http://en.wikipedia.org/wiki/Permutation -- здесь очень хороший алгоритм.
     
  5. murder

    murder Member

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

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

    stellaco New Member

    Публикаций:
    0
  7. Rel

    Rel Well-Known Member

    Публикаций:
    2
    пуффф... вот ты переставляешь элементы последовательности по определенному алгоритму... что мешает тебе выполнить этот алгоритм 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 вроде бы...

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

    SadKo Владимир Садовников

    Публикаций:
    8
    Не 5!, а C из n по k.
     
  9. Pahan

    Pahan New Member

    Публикаций:
    0
    Спасибо за внимание к проблеме.
    2 Forever и Rel.

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

    murder Member

    Публикаций:
    0
    Если перестановок не много можно организовать выборку из таблицы.
     
  11. Rel

    Rel Well-Known Member

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

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

    Forever Виталий

    Публикаций:
    0
    Можно сделат проще, чем длинная арифметика и последовательная генерация. Причем намного.
    Вот смотри. Пусть 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.
     
  13. Y_Mur

    Y_Mur Active Member

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

    murder Member

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

    Pahan New Member

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

    Forever Виталий

    Публикаций:
    0
    Алгоритм, описанный мною выше, подошел или нет?
     
  17. Y_Mur

    Y_Mur Active Member

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

    Forever Виталий

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

    Y_Mur Active Member

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

    murder Member

    Публикаций:
    0