مقدمه
بازم بر میگردیم به set theory
و کاربرد آن در حل مسائل جهان واقعی.
برخی از مسائل را می توانیم توسط
پردازش تمام ترکیبات ممکن بین عناصر آن مجموعه حل کرد. بطور مثال یک راه حل غیر
هوشمندانه برای مساله معروف "کوله پشتی صفر و یک" یا Knapsack Problem) Bin Packing) بدست آوردن تمام ترکیبات ممکن بین عناصر
موجود در مجموعه (که همان Power Set هست) می باشد.
تعریف Power Set
(طبق تعریف
Wiki):
power set
هر مجموعه مثل A شامل تمام زیر مجموعه های A
و نیز مجموعه تهی بعلاوه خودش می باشد. بطور مثال:
A = {a, b, c}
P(A) = {A, empty
set, {a}, {b}, {c}, {a, b},
{a, c}, {b, c}}
برای
تولید زیر ممجوعه ها یک روش این است که از اعداد Binary کمک
بگیریم. 0 به معنای عدم انتخاب و 1 به معنای انتخاب است. با 3 عنصر می توانیم 2 به
توان 3 زیر مجموعه بدست بیاوریم. به تصویر زیر دقت کنید:
اگر
مقادیر a, b, c را متناظر با اعداد 1و 2و 4 بکنیم و هنگامی
که اعداد متنظر دارای مقدار 1 بودند آنگاه آن مقدار انتخاب شود و در غیر اینصورت
انتخاب نشود. مساله حل خواهد بود.
روش دیگر
برای تولید تمام زیر مجموعه ها این است که ابتدا تمام عناصر را جداگانه انتخاب کنیم
و سپس ترکیب دو عنصر باهم دیگر به شرط اینکه دو عنصر با همدیگر برابر نبوده و عنصر
اولی کوچکتر از عنصر دومی باشد و سپس ترکیب سه عنصر با هم به شر اینکه عناصر تکراری
نبوده و عنصر اول کوچکتر از عنصر دوم و عنصر دوم کوچکتر از عنصر سوم باشد.
استفاده از این الگوریتم را به شما واگذار می کنم.
مساله
فرض کنید
ما جدولی داریم دارای دو ستون یکی شماره ترتیبی و دیگری
مقدار منحصر بفرد و هدفمان پیدا کردن تمام زیر مجموعه های ممکنه است.
CREATE TABLE
PowerSet
(nbr INTEGER NOT NULL PRIMARY KEY,
value VARCHAR(10) NOT NULL UNIQUE);
INSERT INTO PowerSet(nbr, value)
VALUES (1, 'a'), (2, 'b'), (3, 'c');
با احتساب مقادیر
فوق نتیجه مورد نظر ما به این شکل است:
The Wanted Result
-----
∅
a
ab
abc
ac
b
bc
c
راه حل
در اینجا تنها به
ارائه یک راه حل که در مقدمه توضیح دادم بسنده می کنم.
SELECT MAX(CASE WHEN v1 = 1
AND nbr = 1
THEN value ELSE '' END) +
MAX(CASE WHEN v2 = 1
AND nbr = 2
THEN value ELSE '' END) +
MAX(CASE WHEN v3 = 1
AND nbr = 3
THEN value ELSE '' END)
FROM PowerSet
CROSS JOIN (VALUES (1, 0,
0, 0),
(2,
0, 0, 1),
(3,
0, 1, 0),
(4,
0, 1, 1),
(5,
1, 0, 0),
(6,
1, 0, 1),
(7,
1 ,1, 0),
(8,
1, 1, 1)
) AS T(n,v1,v2,v3)
GROUP BY
n;