Комбінаторні алгоритми: індекс поєднання, індекс розбиття на підмножини

Короткий передмова
Комбінаторні алгоритми застосовуються досить часто. В інтернеті можна знайти багато інформації стосовно комбінаторних алгоритмів. Однак російськомовний інтернет, в основному, видає найпростіші задачі суцільного перебору (генерації) комбінаторних об'єктів в циклі. Наприклад:
Приклад
// Сполучення по 3 52
for (int i1 = 0; i1 < 50; ++i1)
for (int i2 = i1+1; i2 < 51; ++i2)
for (int i3 = i2+1; i3 < 52; ++i3)
// ...


Індекс поєднання
Кожному поєднанню, перестановки, розміщення та іншим комбінаторних об'єктів можна зіставити індекс — це номер, в якому він з'являється при переборі даним алгоритмом.

Тут ми розглянемо більш складну задачу, вирішення якої в неті я не знайшов (втім, наведу одну посилання, але та формула явно невірна) — виходячи з самого поєднання (в даному випадку набору трьох чисел) знайти його індекс.

Є варіант перебору «в лоб». Включаємо лічильник поєднань, беремо алгоритм вище і поки не дійдемо до потрібного варіанту перебираємо всі підряд. Такий варіант має дуже велику тимчасову складність, тому такий варіант відкинемо.
Покладемо, на вході є числа i1, i2, i3. Нам, насамперед, потрібно їх впорядкувати в порядку зростання (зверніть увагу, що сам алгоритм генерації, наведений вище, видає їх завжди в упорядкованому вигляді, хоча саме поняття «поєднання» передбачає довільний порядок).

Припустимо, для визначеності, після упорядкування i1 = 3, i2 = 7, i3 = 12.
Це означає, що ми «пройшли» всі сполучення, де i1 було рівним 0, 1 і 2.
Для i1 = 0 ми пройшли C(2, 51) сполучень, оскільки індекси i1, i2 пробігають всі комбінації по 2 з 51 числа.
Для i1 = 1 ми пройшли C(2, 50) поєднань.
Для i1 = 2 ми пройшли C(2, 49) поєднань.
Разом ми пройшли СУМА {від n = 0 n = i1-1) C(2, 51-n}.
При i1 = 3 розглянемо вже ті сполучення, які ми пройшли, бігаючи по індексу i2 (а він у нас починається з i2 = i1+1 = 4).
При i2 = 4 пройшли C(1, 47) сполучень, при i2 = 5 пройшли C(1, 46) сполучень, при i2 = 6 пройшли C(1, 45) поєднань.
За повною аналогією, при i2 = 7 розглядаємо поєднання, які пробіг індекс i3.
Отримуємо загальну формулу:
Шуканий індекс поєднання = СУМА {від n = 0 i1-1} C(2, 51-n) + СУМА {від n = i1+1 i2-1} C(1, 51-n) + СУМА {від n = i2+1 з i3-1} C (0, 51-n).

Індекс розбиття на підмножини
У комбінаториці є і більш складний об'єкт — розбиття на підмножини. Наприклад, розбиття 52-елементного безлічі на три підмножини, що складаються відповідно, скажімо, з 2, 3 і 47 елементів, де порядок елементів усередині кожної підмножини неважливий. (До речі сказати, поєднання по 2 з 52 — це просто окремий випадок розбиття на дві підмножини з 2 і 50 елементів відповідно).

Типовий алгоритм генерації полягає в тому, що ми генеруємо поєднання по 2 з 52, і для кожного такого поєднання у вкладеному циклі генеруємо поєднання по 3, 50, причому перевіряємо, щоб індекси (i3, i4, i5) у вкладеному поєднанні не збігалися з індексами (i1, i2) у зовнішньому поєднанні:
Код на C++
// ЗОВНІШНЄ ПОЄДНАННЯ
for (int i1 = 0; i1 < 51; ++i1)
for (int i2 = i1+1; i2 < 52; ++i2)
// ВНУТРІШНЄ СПОЛУЧЕННЯ
for (int i3 = 0; i3 < 50; ++i3)
if (i3 != i1 && i3 != i2)
for (int i4 = i3+1; i4 < 51; ++i4)
if (i4 != i1 && i4 != i2)
for (int i5 = i4+1; i5 < 52; ++i5)
if (i5 != i1 && i5 != i2)
// ...


Знову ж, кожне таке розбиття має свій індекс.
Виявляється, наш алгоритм знаходження індексу поєднання можна модифікувати для знаходження індексу розбиття.
Треба звернути увагу, що індекси у «зовнішньому поєднанні» i1, i2 нам потрібно впорядковувати між собою, а індекси i3, i4, i5 — між собою, але незалежно від перших двох.
Також слід врахувати, що під «вкладеному поєднанні» по суті ми працюємо з 50-елементним безліччю, але індекси i3, i4, i5 потрібно певним чином «зрушити», щоб вони не змінювалися від 0 до 51, а від 0 до 49:
Код на C++
if (i3 >= i1)
--i3;
if (i3 >= i2)
--i2;
// аналогічно для i4, i5


(так сказати, ми вирізаємо з нашого 52-елементного безлічі індекси i1, i2 і потім зрушуємо залишилося безліч, щоб закрити дірки, при цьому зсуваються індекси i3-i5).
Слід врахувати при цьому, що всередині кожного «зовнішнього» поєднання у нас сидить рівно C(3, 50) «вкладених» поєднань.
Тоді алгоритм зведеться до наступного:
ИНДЕКС_СОЧЕТАНИЯ (i1, i2 з 52) * ЧИСЛО_СОЧЕТАНИЙ_ПО_3_ИЗ_50 + ИНДЕКС_СОЧЕТАНИЯ (i3, i4, i5 з 50 після зсуву індексів).

Приведення алгоритмів до константною складності
Відразу повинен звернути увагу, що у формулі виникає помилка, якщо наприклад, i1 = 0 (ми вважаємо суму для n = від 0 до -1) або i2 = 1 (вважаємо суму від 1 до 0). Насправді в таких випадках відповідну суму слід приймати рівною нулю, і результат вийде коректним.
Також повинен звернути увагу на тимчасову складність наших алгоритмів: вони мають лінійну складність при умові, що C ви вважаєте за константна час. Це вже набагато краще, ніж перебір «в лоб».
Але насправді для фіксованої розмірності базового безлічі (у нашому випадку 52) нічого не заважає звести алгоритм до константною складності. Для цього застосуємо знання математики і аналітично порахуємо суми.
Наприклад, число поєднань C(2, K), якщо «розкрити» його у вигляді формули K! / ((K-2)! * 2!), наводиться до многочленом 2-го ступеня. А оскільки він у нас під знаком суми, то можна застосувати формули суми N-х ступенів чисел натурального ряду (див. Вікіпедія) і отримати один-єдиний многочлен 3-ї степені. Який, очевидно, має константну тимчасову складність. (Причому «помилка», яку я навів на початку підзаголовка, ніяк себе не проявляє, формула залишається коректною).
Повторюся, це для фіксованої розмірності базового безлічі. Втім, впевнений, з допомогою метапрограммирования можна «навчити» компілятор, щоб він робив цю роботу за вас.
Приклад коду для індексу розбиття на 2, 3, 47
int get_split_2_3_47_index(int i1, int i2, int i3, int i4, int i5)
{
// Індекс поєднання по 2 з 52, помножений на C(3, 50)
int offset = (
(52*51 - (51-i1)*(52-i1)) / 2
+ (i2 - i1 - 1)
) * 19600;

// "Переиндексируем" внутрішню групу так, щоб була нумерація 0...49
if (i3 >= i1)
--i3;
if (i3 >= i2)
--i3;
if (i4 >= i1)
--i4;
if (i4 >= i2)
--i4;
if (i5 >= i1)
--i5;
if (i5 >= i2)
--i5;

// Тепер додамо індекс комбінації по 3
// 0:
// СУМА для n = 0 за i3-1 СПОЛУЧЕНЬ (2, 49-n)
// = СУМА для m = 50-i3 по 49 (m * (m-1) / 2)
offset += (19600
- (
((49-i3)*(50-i3)*(99-2*i3)) / 6
- ((49-i3)*(50-i3)) / 2
) / 2
);

// 1:
// СУМА для n = i3+1 з i4-1 СПОЛУЧЕНЬ (1, 49-n)
offset += (((48-i3)*(49-i3) - (49-i4)*(50-i4)) / 2);

// 2:
// СУМА для n = i4+1 за i5-1 (1)
offset += (i5 - i4 - 1);

return offset;
}



Післямова
Мені в своєму симуляторі покеру (Texas hold'em) захотілося заздалегідь розрахувати і зберігати ймовірності виграшу для всіх можливих сполучень з моїх ручних карт (2 штуки) і всіх карт флопа (3 карти на столі). Це відповідає розподіленню 52-множини на 2, 3, 47 підмножини.
Розрахував і зберіг.
Але коли прийшов час прочитати дані з файлу для конкретної комбінації, вже дуже мені не хотілося щось там довго обчислювати або здійснювати пошук в гигабайтном файлі. Тепер я просто визначаю зміщення в файлі і зчитую безпосередньо те, що мені треба.

Взагалі, комбінаторні алгоритми я розбив би на такі класи:
  • Генерація комбінаторних об'єктів в єдиному циклі (тут все просто, приклади я навів);
  • Перехід до наступного (або попереднього) комбінаторної об'єкту, знаючи попередній (свого роду forward/backward iterator, висловлюючись у термінах C++) — тут можна відзначити навчальний посібник Т. В. Федоряевой, де наводиться алгоритм константною тимчасової складності для перестановок, так і інші приклади в неті можна знайти, але тільки для перестановок — а було б цікаво побачити аналогічні алгоритми і для інших комбінаторних об'єктів;
  • Знаходження індексу об'єкта. Тут прикладів зовсім немає, виключаючи посібник Федоряевой, причому лінійної складності і тільки для перестановки;
  • Знаходження об'єкта по індексу.
Було б цікаво отримати довідник по комбінаторних алгоритмів для всіх комбінаторних об'єктів, включаючи, перестановки, сполучення, розміщення, розбиття на підмножини, сполучення з повтореннями, розміщення з повтореннями.

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.