Надмірність поєднань

Відразу зазначу, що дана замітка більше дискусійна, ніж згідно з якою. В Інтернет можна знайти досить багато описів та реалізацій алгоритмів генерації поєднань. Тим не менш, ймовірно, можна виділити два основних — рекурсивний і той ітераційний алгоритм, який опубліковано в книзі Липського «Комбінаторика для програмістів». Можливо, є якісь алгоритми, що істотно відрізняються від наведених. Принаймні, цілком справедливо припустити, що поєднання можна генерувати за допомогою псевдовипадкових чисел, але це, ймовірно, — самий довгий шлях. Незважаючи на достатню стислість і витонченість алгоритму з книги Липського, він мені не здався зовсім простим, а деякі інші реалізації бачаться досить заплутаними. Приклад.

Моя ідея

Я вирішив спробувати вивести алгоритм генерації поєднань в більш доступній формі, нехай з деяким збитком для часу виконання або відповідності формулі. Спробую відразу показати на прикладі свою ідею. Є вхідний масив А=12345, n=5, припустимо, =3.
Для формування поєднань пропонується наступне:
1) Створити матрицю з елементів масиву елементів, наприклад, двовимірний масив виду:

123
234
345


2) Другим кроком перебирати масив А у циклі з 1 до n і підставляти кожен елемент А на кожну позицію в матриці.
3) Друкувати кожну підстановку.

В принципі це все. В результаті роботи будуть сформовані всі поєднання, але з дублікатами. Щоб зменшити надмірність, можна не підставляти елемент А в ті подмассивы, в яких він вже присутній.

Для порівняння наведу результат роботи суворого алгоритму і цього. Для
n=7, k=4 — це 35 унікальних поєднань, як і повинно бути за формулою. Даний алгоритм генерує 44 поєднання, тобто серед них 9 дублікатів.

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

Я не хотів спочатку публікувати код, але щоб замітка не здавалася зовсім теоретичної, ховаю під спойлер прототип (можна сказати, перший начерк) даного алгоритму на PHP:
Код алгоритму. PHP
$a = array(
1,
2,
3,
4,
5
);
$n = count($a);
$k = 2;

//Формування двовимірного масиву по k

$b = array();
$j = 0;

while ($j != $n - $k + 1)
{
$i = 0;
while ($i != $k)
{
$b[$j][$i] = $a[$i];
$i++;
}

$j++;
array_shift($a);
}

//Обхом матриці з підстановкою елемента

function change($val, $i, $k)
{
$j = 0;
print_r($val);
print '<br/>';
while ($j != $k)
{
$c = $val;
while (true)
{
$c[$j] = $i;
print_r($c);
print '<br/>';
unset($c);
break;
}

$j++;
}
}

$i = 1;

while ($i != $n)
{
foreach($b as $val)
{
if (!in_array($i $val))
{
change($val, $i, $k);
}
}

$i++;
}



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

0 коментарів

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