Помогите найти закономерность в последовательности

[granit201z]

Сразу простите за неграмотно-математическую речь.
Хочу написать простейший алгоритм для вычисления всех перестановок из n элементов. В простейшем случае взял $n = 4$. Получаются такие перестановки:

$( 1234, 1243, 1324, 1342, 1423, 1432, 2134, 2143, 2314, 2341, 2413, 2431, 3124, 3142, 3214, 3241, 3412, 3421, 4123, 4132, 4213, 4231, 4312, 4321 )$

Если рассматривать вышеприведенные комбинации цифр как числа, то вырисовывается некоторая последовательность разностей между $k+1$ и $k$ членами, а именно:

$(9, 81, 18, 81, 9, 702, 9, 171, 27, 72, 18, 693, 18, 72, 27, 171, 9, 702, 9, 81, 18, 81, 9)$

Оказалось, что эта последовательность справедлива и для первых 24-членов перестановок при $n = 5$, т.е.:

($12345$, $12345+9=12354$, $...+81=12435$, $...+18=12453$, $...+81=12534$, $...+9=12543$, $...+702=13245$, $...+9=13254$, $...+171=13425$, $...+27=13452$, $...+72=13524$, $...+18=13542$, $...+693=14235$, $...+18=14253$, $...+72=14325$, $...+27=14352$, $...+171=14523$, $...+9=14532$, $...+702=15234$, $...+9=15243$, $...+81=15324$, $...+18=15342$, $...+81=15423$, $...+9=15432$)

Так же оказалось, что первые 5 членов "последовательности разностей" справедливы для перестановок при $n = 3$, а еще они симметричны относительно члена 18, как и в последовательности для $n = 4$ наблюдается симметрия относительно члена 693.

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

[Someone]

Это ведёт в тупик. Просто перечисляйте в лексикографическом порядке. Могли бы Гуглом найти.

[granit201z]

Someone в сообщении #1339450 писал(а):

Это ведёт в тупик

т.е. вывести какую-то обобщенную формулу не получится?

[Someone]

Нет. Но алгоритм генерации перестановок в лексикографическом порядке в интернете найти нетрудно.

P.S. Но место для темы выбрано неудачно. Это куда-нибудь в программирование надо (здесь же, на dxdy).

[grizzly]

granit201z
Очень интересное наблюдение. Посмотрите A209280 и, ещё лучше, A217626 -- в ней приведены какие-то наблюдения, гипотезы, возможности применения. Посмотрите дальше по ссылкам от этих последовательностей -- там тоже есть забавные вещи. Или найдите другие последовательности того же автора -- я буквально на днях чем-то похожим увлёкся и заполнил его имя.

[granit201z]

grizzly в сообщении #1339454 писал(а):

Посмотрите A209280

Спасибо за ссылки. А вот эта A209280 это ж по сути она и есть, кажется

[grizzly]

granit201z в сообщении #1339458 писал(а):

А вот эта A209280 это ж по сути она и есть, кажется

Другая по сути тоже (её, грубо говоря, на 9 поделили). Но там больше информации.

[granit201z]

Еще одно свойство у нее нашел. Сумма ее первых членов (если номер члена факториальный) увеличивается в 10 раз по отношению к предыдущему факториальному члену.
т.е.:
для 1-го: 1! - $9$
для 2-го: 2! - $9+81 = 90$
для 6-го: 3! - $9+81+18+81+9+702 = 900$
для 24-го: 4! - $9+81+18+81+9+702+9+171+27+72+18+693+18+72+27+171+9+702+9+81+18+81+9+5913 = 9000$

Остальные не проверял. Но, наверное тоже

[grizzly]

granit201z в сообщении #1339493 писал(а):

Но, наверное тоже

Да, по крайней мере до 10! (пока цифры не закончатся, потом нужно будет договариваться, что значит эта последовательность дальше).

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

[granit201z]

Еще одно свойство. Сформулировать словами я его не могу. Но могу показать:
Каждый факториальный член можно найти по определенному правилу:
для 2!: $123-21=102; 102-21=81$
для 3!: $1234-211=1023; 1023-321=702$
для 4!: $12345-2111=10234; 10234-4321=5913$
для 5! (не проверял, но предполагаю): $123456-21111=102345; 102345-54321=48024 $
В принципе, на этих свойствах уже можно построить ее первые 6 членов:

первый равен 9;
сумма первого и второго, т.к. второй на факториальном месте $(2!)$ должна быть в 10 раз больше суммы предыдущего факториального места, т.е. $9\cdot10=90$, следовательно $90-9=81$;
шестой член, т.е. 3! строится из свойства $1234-211=1023; 1023-321=702;$
из свойства о том, что ее члены симметричны относительно элемента с номером n!/2 строятся 4 и 5 члены, равные соответственно 81 и 9;
Теперь известны 5 членов из 6-ти и известно, что сумма первых 6-ти должна быть в 10 раз больше, чем сумма первых 2-х, т.е. $90\cdot10=900$. Отсюда 3-й член: $900-702-9-81-81-9=18$

Дальше пока что не придумал ничего

[ozheredov]

granit201z

Вы хотите создать генератор, производящий перестановки быстрее чем стандартный «лексикографический», который упомянут пользователем Someone? До какого размера выборки будете скармливать?

Лайфхак: на практике нужная перестановка найдётся быстрее, ежели не устраивать полный перебор, а искать её монтекарлой через randpermutation()

[arseniiv]

Случайную перестановку тоже сгенерировать уметь надо.

[granit201z]

ozheredov в сообщении #1339826 писал(а):

granit201z

Вы хотите создать генератор, производящий перестановки быстрее чем стандартный «лексикографический», который упомянут пользователем Someone? До какого размера выборки будете скармливать?

Лайфхак: на практике нужная перестановка найдётся быстрее, ежели не устраивать полный перебор, а искать её монтекарлой через randpermutation()

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

[Someone]

granit201z в сообщении #1339854 писал(а):

Вообще, изначально я хотел написать программку для нахождения определителя матрицы.

Способ хуже придумать трудно. Но если очень хочется, то можно написать рекурсивный алгоритм: разложить определитель по первой строке, а алгебраические дополнения считать этим же алгоритмом. Это будет то же самое, только без мороки с генерацией перестановок, но с ещё большими затратами времени. Или всё-таки используйте лексикографический алгоритм. Для определителей небольшого размера затраты времени будут небольшими, но с увеличением размера они растут очень быстро.

P.S. Когда мы на втором, кажется, курсе изучали программирование (для начала — в машинных кодах), я написал такую программу (именно в машинных кодах). Было весьма утомительно. Потом от машинных кодов перешли к автокоду (вроде бы, предшественник ассемблера; компилировать в машинные коды предполагалось вручную). Потом изучали Алгол-60.

[ozheredov]

arseniiv в сообщении #1339834 писал(а):

Случайную перестановку тоже сгенерировать уметь надо.

Обычно для этого есть стандартный метод randpermutation, он опрьимизирован на уровне чуть ли не машинного кода. А если за перформанс рейтом не гоняться, можно запросто навелосипедить типа «для первого объекта случайно выбираем позицию, для последующих позицию выбираем случайно из тех, которые свободны»

-- 18.09.2018, 21:37 --

Someone в сообщении #1339882 писал(а):

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

... и здравствуй, Переполнение стека вызовов )))