1 Востаннє редагувалося leofun01 (15.07.2021 23:32:39)

Тема: Генерація перестановок заданої довжини і з заданими розмірами циклів.

Кожна перестановка (в межах цієї задачі) представлена послідовністю цифр (шіснадцяткових, але це не впливає на розвязок), і може бути представлена множиною циклів (теж із цифр).

Приклади

Приклад 0:
0123456789ABCDEF
- це 0-елемент серед перестановок. Додавання такої перестановки до будь-якої перестановки X дасть перестановку X.
Ця перестановка має 16 циклів розміром 1:
(0)(1)(2)(3)(4)(5)(6)(7)(8)(9)(A)(B)(C)(D)(E)(F)
Інформацію про кількість і розміри циклів для цього прикладу запишемо так:

{
    1 : 16
}

Нижче буде пояснено чому ми вибрали таке позначення.
Математики в багатьох випадках не розглядають одиничні цикли, але в межах цієї задачі їх доведеться враховувати.

Приклад 1:
0123456789ABCDEF
401238567B9AFCDE
Ця перестановка має 4 цикли різних розмірів:
(04321)(5876)(9BA)(CFED)
1 цикл  розміром 5
2 цикли розміром 4
1 цикл  розміром 3
Інформацію про кількість і розміри циклів зручно зберігати як словник (dictionary):

{
    3 : 1,
    4 : 2,
    5 : 1
}

Приклад 2:
0123456789ABCDEF
E1F3CAB264D89507
Ця перестановка має 7 циклів різних розмірів:
(0E)(1)(2F7)(3)(4C9)(5AD)(6B8)
1 цикл  розміром 2
2 цикли розміром 1
4 цикли розміром 3
Відповідно:

{
    1 : 2,
    2 : 1,
    3 : 4
}

Всі приклади які ми поки розглянули були для перестановок довжиною 16 цифр.

Задача:
Згенерувати всі перестановки заданої довжини і з заданими розмірами циклів.
Для простоти введемо обмеження:
1 <= Довжина перестановки <= 16;
1 <= Довжина циклу <= 16;
1 <= Кількість циклів <= 16;

Я хочу зробити це як функцію, якій на вхід я буду подавати (як параметр) екземпляр словника, в якому міститься інформація про кількість і розміри циклів. Ясно що будуть ще якісь допоміжні функції. Але я застряг на алгоритмі.

Історія фейлів

Перша спроба провалилась:
Я намагався зробити все максимально просто. Послідовно генерував всі перестановки заданої довжини (незалежно від того, які там розміри циклів), для кожної перевіряв чи має ця перестановка всі потрібні цикли, і якщо все ok, то повертав її користувачу.
Такий підхід виявився дуже поганим по перформансу. Він дає правильні результати, але іноді їх не реально дочекатись.

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

В цілому спроб було багато, але здається я не в ту сторону копаю.

Може хто зтикався з подібною задачою, дайте знати як рішати цю поїботу.

Повязані топіки

До речі, ця задача безпосередньо повязана з теорією груп. Там перестановки є елементами груп.

2

Re: Генерація перестановок заданої довжини і з заданими розмірами циклів.

Довжину перестановки обчислюємо як суму добутків ключа і значення зі словника-параметра.

Приклад:

{
    3 : 1,
    4 : 2,
    5 : 1
}

3*1 + 4*2 + 5*1 == 16

3

Re: Генерація перестановок заданої довжини і з заданими розмірами циклів.

А я колись радів, що теорію груп у нас викладали (і приймали) дуже спрощено, фактично й не викладали...

Подякували: leofun011

4

Re: Генерація перестановок заданої довжини і з заданими розмірами циклів.

Виправив

Приклад 1:
401238567B9AFCDE
...
(01234)(5678)(9AB)(CDEF)

Я тут помилився. Вже виправив.

Має бути так:
0123456789ABCDEF
401238567B9AFCDE
(04321)(5876)(9BA)(CFED)

Або так:
0123456789ABCDEF
123406785AB9DEFC
(01234)(5678)(9AB)(CDEF)