Пару дней назад был опубликован пост с решением на MySQL загадки Джиндоша (она же загадка Эйнштейна).
Предложенное решение показалось мне "неспортивным" - ведь помимо необходимости жестко учитывать в структуре запроса количество исходных элементов ("джойнить" нужные таблицы нужное количество раз), так еще и условия в запросе приходилось многократно дублировать:
-- Рядом с дамой с портсигаром сидит дама из Морли
AND
(
(t1.item='cigar-case' AND t2.city='Morley') OR
(t2.item='cigar-case' AND 'Morley' IN (t1.city, t3.city)) OR
(t3.item='cigar-case' AND 'Morley' IN (t2.city, t4.city)) OR
(t4.item='cigar-case' AND 'Morley' IN (t3.city, t5.city)) OR
(t5.item='cigar-case' AND t4.city='Morley')
)
Поэтому я попробовал решить эту задачу "в общем виде", используя возможности PostgreSQL, и вот что из этого получилось.
Полный текст загадки и ее перевод можно увидеть в оригинальном посте, здесь я буду пользоваться теми же значениями, которые приведены и там.
Для начала, договоримся, что все значения всех атрибутов (имена, цвета, города, напитки и ценности) у нас будут полностью уникальны, тогда их полный набор можно представить в виде двумерного текстового массива, а их названия и вовсе не будут нас интересовать:
-- исходные наборы атрибутов
WITH RECURSIVE attr AS (
SELECT '{
{Winslow,Marcolla,Contee,Natsiou,Finch}
, {red,white,purple,blue,green}
, {Bailton,Serkonos,Freiport,Morley,Danuol}
, {absent,coctail,rum,cider,whiskey}
, {ring,diamond,order,cigar-case,coulomb}
}'::text[][] src
)
Вычислим размерность этого набора (она же - количество участвующих персон), чтобы использовать его в дальнейшем:
-- количество атрибутов (= персон)
, qty AS (
SELECT array_length((TABLE attr), 1) qty
)
Сгенерируем все возможные комбинации атрибутов, воспользовавшись методикой из статьи "SQL HowTo: ломаем мозг об дерево — упорядочиваем иерархию с рекурсией и без". В нашем случае у нас всего 5 позиций по 5 вариантов в каждой - то есть 5 ^ 5 = 3125
комбинаций:
-- все комбинации атрибутов
, comb_attr AS (
SELECT
ARRAY(
SELECT
attr[j + 1][((i / (qty ^ j)::integer) % qty) + 1]
FROM
generate_series(0, qty - 1) j
) c
FROM
attr
, qty
, generate_series(0, (qty ^ qty)::integer - 1) i
)
Фактически, здесь мы сгенерировали все возможные N-значные числа в N-ричной системе счисления, дающие нам все возможные комбинации, взяв для каждой "цифры" соответствующее значение атрибута:
с
text[]
{Winslow,red,Bailton,absent,ring}
{Marcolla,red,Bailton,absent,ring}
{Contee,red,Bailton,absent,ring}
{Natsiou,red,Bailton,absent,ring}
{Finch,red,Bailton,absent,ring}
{Winslow,white,Bailton,absent,ring}
{Marcolla,white,Bailton,absent,ring}
{Contee,white,Bailton,absent,ring}
...
Оставим среди них только те, которые соответствуют известным условиям для каждой отдельной персоны:
-- разрешенные комбинации
, cond_single AS (
SELECT
*
FROM
comb_attr
, unnest(ARRAY[1,2,3,4,5]) pos -- генерируем варианты мест
WHERE
-- Уинслоу ... синее
('{Winslow,blue}'::text[] <@ c OR NOT ('{Winslow,blue}'::text[] && c)) AND
-- Марколла левее всех
(('Marcolla' = ANY(c) AND pos = 1) OR ('Marcolla' <> ALL(c) AND pos <> 1)) AND
-- красное ... виски
('{red,whiskey}'::text[] <@ c OR NOT ('{red,whiskey}'::text[] && c)) AND
-- Морли ... зелёное
('{Morley,green}'::text[] <@ c OR NOT ('{Morley,green}'::text[] && c)) AND
-- Финч ... Кулон
('{Finch,coulomb}'::text[] <@ c OR NOT ('{Finch,coulomb}'::text[] && c)) AND
-- Фрейпорт ... Перстень
('{Freiport,ring}'::text[] <@ c OR NOT ('{Freiport,ring}'::text[] && c)) AND
-- Конти ... абсент
('{Contee,absent}'::text[] <@ c OR NOT ('{Contee,absent}'::text[] && c)) AND
-- Серконос ... сидр
('{Serkonos,cider}'::text[] <@ c OR NOT ('{Serkonos,cider}'::text[] && c)) AND
-- посередине ... ром
(('rum' = ANY(c) AND pos = 3) OR ('rum' <> ALL(c) AND pos <> 3)) AND
-- Нациу ... Бейлтон
('{Natsiou,Bailton}'::text[] <@ c OR NOT ('{Natsiou,Bailton}'::text[] && c))
)
Здесь '{Winslow,blue}'::text[] <@ c
означает вхождение массива значений в массив комбинации - то есть оба элемента присутствуют в наборе, а NOT ('{Winslow,blue}'::text[] && c)
- обратное ему "не присутствует ни один". Соответственно, 'Marcolla' = ANY(c) AND pos = 1
и обратное ему 'Marcolla' <> ALL(c) AND pos <> 1
учитывают условие позиции.
Тут мы не делаем никаких дополнительных логических вычислений, типа "Марколла левее всех, рядом с гостьей, одетой в белое, значит, одетая в белое - на втором месте" - нет, просто заносим исходные условия.
Теперь воспользуемся мощью рекурсии и сгенерируем все варианты "рассадки" по местам (pos
), так, чтобы ни одно значение ни одного атрибута не повторялось:
-- рекурсивно отсекаем повторяемость значений
, r AS (
SELECT
0 pos
, '{}'::text[] acc
UNION ALL
SELECT
cs.pos
, r.acc || cs.c -- добавляем комбинацию в накопленное
FROM
r
JOIN
cond_single cs
ON cs.pos = r.pos + 1 AND -- следующая позиция
NOT (cs.c && r.acc) -- нет пересечений атрибутов
)
Среди всех таких "цепочек" нас интересуют только те, которые дошли до последней позиции - то есть когда удалось рассадить всех (pos = qty
). Пронумеруем их с помощью row_number() OVER()
на группы и "нарежем" в наборы для каждой персоны:
-- комбинации размещения
, comb_person AS (
SELECT
grp
, i + 1 pos
, acc[i * qty + 1 : (i + 1) * qty] c -- слайс массива
FROM
qty
, LATERAL (
SELECT
row_number() OVER() grp -- нумеруем группы
, *
FROM
r
WHERE
pos = qty -- только полные размещения
) T
, generate_series(0, qty - 1) i
)
grp | pos | c
bigint | integer | text[]
1 | 1 | {Marcolla,purple,Danuol,coctail,cigar-case}
1 | 2 | {Natsiou,red,Bailton,whiskey,order}
1 | 3 | {Finch,green,Morley,rum,coulomb}
1 | 4 | {Winslow,blue,Serkonos,cider,diamond}
1 | 5 | {Contee,white,Freiport,absent,ring}
2 | 1 | {Marcolla,red,Danuol,whiskey,cigar-case}
2 | 2 | {Natsiou,purple,Bailton,coctail,order}
2 | 3 | {Finch,green,Morley,rum,coulomb}
2 | 4 | {Winslow,blue,Serkonos,cider,diamond}
2 | 5 | {Contee,white,Freiport,absent,ring}
3 | 1 | {Marcolla,green,Morley,coctail,order}
...
Осталось определить те группы (то есть комбинации размещения персон), для которых выполняются все "парные" условия одновременно - для этого воспользуемся агрегатной функцией bool_or
для каждого из них в HAVING
-части запроса:
SELECT
grp
FROM
comb_person X
JOIN
comb_person Y
USING(grp)
GROUP BY
1
HAVING
-- Марколла ... рядом с ... белое
bool_or('Marcolla' = ANY(X.c) AND 'white' = ANY(Y.c) AND abs(X.pos - Y.pos) = 1) AND
-- красное ... слева от ... пурпурное
bool_or('red' = ANY(X.c) AND 'purple' = ANY(Y.c) AND X.pos = Y.pos - 1) AND
-- Портсигар ... рядом с ... Морли
bool_or('cigar-case' = ANY(X.c) AND 'Morley' = ANY(Y.c) AND abs(X.pos - Y.pos) = 1) AND
-- Бриллиант ... рядом с ... Дануолл
bool_or('diamond' = ANY(X.c) AND 'Danuol' = ANY(Y.c) AND abs(X.pos - Y.pos) = 1) AND
-- Дануолл ... коктейль ... соседки
bool_or('Danuol' = ANY(X.c) AND 'coctail' = ANY(Y.c) AND abs(X.pos - Y.pos) = 1)
Здесь условия "рядом с" и "соседки" мы трансформировали в abs(X.pos - Y.pos) = 1
.
Остался последний шаг - вывести содержимое всех групп, удовлетворяющих всем условиям сразу:
SELECT
pos
, c person
FROM
comb_person
WHERE
grp IN (
...
)
ORDER BY
grp, pos;
В нашем примере решение выведется единственное:
pos | person
integer | text[]
1 | {Marcolla,green,Morley,coctail,diamond}
2 | {Contee,white,Danuol,absent,cigar-case}
3 | {Winslow,blue,Freiport,rum,ring}
4 | {Natsiou,red,Bailton,whiskey,order}
5 | {Finch,purple,Serkonos,cider,coulomb}
То есть ответ на загадку:
Ценность | Дама |
Портсигар | графиня Конти |
Орден | мадам Нациу |
Перстень | леди Уинслоу |
Бриллиант | доктор Марколла |
Весь же решающий запрос принимает такой итоговый вид:
-- исходные наборы атрибутов
WITH RECURSIVE attr AS (
SELECT '{
{Winslow,Marcolla,Contee,Natsiou,Finch}
, {red,white,purple,blue,green}
, {Bailton,Serkonos,Freiport,Morley,Danuol}
, {absent,coctail,rum,cider,whiskey}
, {ring,diamond,order,cigar-case,coulomb}
}'::text[][] attr
)
-- количество атрибутов (= персон)
, qty AS (
SELECT array_length((TABLE attr), 1) qty
)
-- все комбинации атрибутов
, comb_attr AS (
SELECT
ARRAY(
SELECT
attr[j + 1][((i / (qty ^ j)::integer) % qty) + 1]
FROM
generate_series(0, qty - 1) j
) c
FROM
attr
, qty
, generate_series(0, (qty ^ qty)::integer - 1) i
)
-- разрешенные комбинации
, cond_single AS (
SELECT
*
FROM
comb_attr
, unnest(ARRAY[1,2,3,4,5]) pos -- генерируем варианты мест
WHERE
-- Уинслоу ... синее
('{Winslow,blue}'::text[] <@ c OR NOT ('{Winslow,blue}'::text[] && c)) AND
-- Марколла левее всех
(('Marcolla' = ANY(c) AND pos = 1) OR ('Marcolla' <> ALL(c) AND pos <> 1)) AND
-- красное ... виски
('{red,whiskey}'::text[] <@ c OR NOT ('{red,whiskey}'::text[] && c)) AND
-- Морли ... зелёное
('{Morley,green}'::text[] <@ c OR NOT ('{Morley,green}'::text[] && c)) AND
-- Финч ... Кулон
('{Finch,coulomb}'::text[] <@ c OR NOT ('{Finch,coulomb}'::text[] && c)) AND
-- Фрейпорт ... Перстень
('{Freiport,ring}'::text[] <@ c OR NOT ('{Freiport,ring}'::text[] && c)) AND
-- Конти ... абсент
('{Contee,absent}'::text[] <@ c OR NOT ('{Contee,absent}'::text[] && c)) AND
-- Серконос ... сидр
('{Serkonos,cider}'::text[] <@ c OR NOT ('{Serkonos,cider}'::text[] && c)) AND
-- посередине ... ром
(('rum' = ANY(c) AND pos = 3) OR ('rum' <> ALL(c) AND pos <> 3)) AND
-- Нациу ... Бейлтон
('{Natsiou,Bailton}'::text[] <@ c OR NOT ('{Natsiou,Bailton}'::text[] && c))
)
-- рекурсивно отсекаем повторяемость значений
, r AS (
SELECT
0 pos
, '{}'::text[] acc
UNION ALL
SELECT
cs.pos
, r.acc || cs.c -- добавляем комбинацию в накопленное
FROM
r
JOIN
cond_single cs
ON cs.pos = r.pos + 1 AND -- следующая позиция
NOT (cs.c && r.acc) -- нет пересечений атрибутов
)
-- комбинации размещения
, comb_person AS (
SELECT
grp
, i + 1 pos
, acc[i * qty + 1 : (i + 1) * qty] c -- слайс массива
FROM
qty
, LATERAL (
SELECT
row_number() OVER() grp
, *
FROM
r
WHERE
pos = qty -- только полные размещения
) T
, generate_series(0, qty - 1) i
)
SELECT
pos
, c person
FROM
comb_person
WHERE
grp IN (
SELECT
grp
FROM
comb_person X
JOIN
comb_person Y
USING(grp)
GROUP BY
1
HAVING
-- Марколла ... рядом с ... белое
bool_or('Marcolla' = ANY(X.c) AND 'white' = ANY(Y.c) AND abs(X.pos - Y.pos) = 1) AND
-- красное ... слева от ... пурпурное
bool_or('red' = ANY(X.c) AND 'purple' = ANY(Y.c) AND X.pos = Y.pos - 1) AND
-- Портсигар ... рядом с ... Морли
bool_or('cigar-case' = ANY(X.c) AND 'Morley' = ANY(Y.c) AND abs(X.pos - Y.pos) = 1) AND
-- Бриллиант ... рядом с ... Дануолл
bool_or('diamond' = ANY(X.c) AND 'Danuol' = ANY(Y.c) AND abs(X.pos - Y.pos) = 1) AND
-- Дануолл ... коктейль ... соседки
bool_or('Danuol' = ANY(X.c) AND 'coctail' = ANY(Y.c) AND abs(X.pos - Y.pos) = 1)
)
ORDER BY
grp, pos;
При этом нас больше не волнует ни общее количество атрибутов в задаче, ни их названия - только лишь вбивай известные условия.