Задачка по комбинаторике. Сделать SQL запрос или алгоритм. @ DeForum.ru

34 Сообщения: 1866 Зарегистрирован: 17.02.04

Есть таблица индексов(id) и их значений(value), к примеру:

Код:

id|value
--+-------
| a
| b
| c
| d
| e
| f

В таблицу могут добавляться новые пары, например: 1-f, 1-h, 4-a, 4-b.

Задача: найти все возможные комбинации значений (value).
Условие: в комбинации индексы должны быть уникальными.

Пример 1:
Комбинация a,c,f является верной. Если заменить value на id то получим: 1,2,3 (индексы являются уникальными).

Пример 2:
Комбинация a,b,f является не верной. Если заменить value на id то получим: 1,1,3 (индексы не являются уникальными).

Для простоты предлагаю использовать: псевдо-язык, SQL запросы или диаграммы.
Или просто подскажите ссылки на похожие задачи и алгоритмы. :beer:

И в чем, собственно, проблема? Не устраивает очевидное решение сложности O(n!) ?

34 Сообщения: 1866 Зарегистрирован: 17.02.04

Crazy,
я в этом ничего не понимаю. Незнаю что значит "О" :lamer:

AlexShop писал(а):

см. Big O Notation

34 Сообщения: 1866 Зарегистрирован: 17.02.04

Crazy,
да я помню про это, но не был уверен что это то самое "O"

Над решением еще работаю (или есть где в интернете стандартное решение?)

AlexShop, решение -- полный перебор. Никакого rocket science. Единственная эвристика -- перебирать индексы и для каждой комбинации перебирать подстановки значений.

34 Сообщения: 1866 Зарегистрирован: 17.02.04

Вот что получилось:

Код:

function permutations($arrays, $i = 0, $combination = array())
{
    global $result;
    if (! isset($arrays[$i])) {$result[] = $combination;}
    
    foreach((array) $arrays[$i] as $value):
        $combination[$i] = $value;
        permutations($arrays, $i + 1, $combination);
    endforeach;
}
    
// ТЕСТИРОВАНИЕ
// Можно использовать любой 2-х мерный массив
$arrays = array
(
    array('a', 'b', 'c'),
    array('1', '2', '3'),
    array('A', 'B')
);
    
permutations($arrays);
print_r($result);

Аналогичная задача, только вместо таблицы я использовал двух-мерный PHP массив.
Задача та же: найти все возможные комбинации, взяв по одному элементу из каждого суб-массива.

Единственное, пока не удалось избавиться от глобальной переменной.
Думаю все организовать в класс и глобальная переменная будет свойством класса.

DeДверь
Логин:
Пароль:
	Автологин