هفتمین چالش SQL (بررسی دو به دو مشترک بودن مجموعه ها)

[محمد سلیم آبادی]

97070

با حل این مساله به زبان SQL شاهد قابلیت های ذهنی خود خواهید بود.

توضیح تکمیلی:
لیست تمام ترکیبات 2 از 4 برابر است با:

{ {a, b}, {a, c}, {a, d}, {b, c}, {b, d}, {c, d} }
پس باید بین این زوج مجموعه ها عنصر مشترک وجود داشته باشد تا "دو به دو مشترک" باشند.

برای تست راه حل از اسکریپت زیر استفاده شود.

create table table_1
([group] int not null,
element int not null,
primary key([group], element));

insert into table_1
values (1,3),(1,5),(1,6),
(2,4),(2,6),(2,7),
(3,4),(3,5),(3,8),
(4,3),(4,7),(4,8);

راه حل های پذیرفته شده:
1-cherchil_era
مرحبا به این راه حل

SELECT CASE SUM([Count])%((SUM([sum]) * (SUM([sum]) -1)))
WHEN 0 THEN 'Yes'
ELSE 'No'
END
FROM (
SELECT COUNT(g2) AS [Count],1 AS [SUM]
FROM (
SELECT t1.[group] AS g1,
t2.[group] AS g2
FROM dbo.Table_1 AS t1
LEFT OUTER JOIN dbo.Table_1 AS t2
ON t1.element = t2.element
AND t1.[group] <> t2.[group]

GROUP BY
t1.[group],
t2.[group]

) AS t
GROUP BY g1
) AS result



2-behrouzlo

SELECT ( CASE WHEN SUM(P) = ( SELECT ( COUNT(DISTINCT [group]) - 1 )
* ( COUNT(DISTINCT [group]) )
FROM table_1
) THEN 'Yes'
ELSE 'No'
END ) Result
FROM ( SELECT T1.[group] ,
1 P
FROM dbo.table_1 T1
CROSS APPLY ( SELECT *
FROM dbo.table_1 T2
WHERE T1.[group] <> T2.[group]
AND T1.element = T2.element
) L
GROUP BY T1.[group] ,
L.[group]
) T



3-msalim

SELECT ( CASE WHEN COUNT(*) = POWER((SELECT COUNT(DISTINCT [group]) FROM table_1), 2)
THEN 'Yes'
ELSE 'No'
END ) Result
FROM ( SELECT T1.[group]
FROM dbo.table_1 T1
INNER JOIN dbo.table_1 T2
ON T1.element = T2.element
GROUP BY T1.[group] ,
T2.[group]
) T



4-msalim

SELECT CASE COUNT(g2) % POWER(COUNT(DISTINCT g1),2)
WHEN 0 THEN 'Yes'
ELSE 'No'
END
FROM (
SELECT t1.[group] AS g1,
t2.[group] AS g2
FROM dbo.Table_1 AS t1
LEFT OUTER JOIN dbo.Table_1 AS t2
ON t1.element = t2.element
GROUP BY
t1.[group],
t2.[group]
) AS result



5-msalim

select case
when not exists (select g1.[Group]
from dbo.Table_1 g1, dbo.Table_1 g2
where g1.Element = g2.Element
group by g1.[Group]
having count(distinct g2.[Group]) <
(select count(distinct [Group]) from dbo.Table_1))
then 'Yes'
else 'No'
End as result;

[cherchil_hra]

SELECT CASE SUM([Count])% SUM([sum])
WHEN 0 THEN 'Yes'
ELSE 'No'
END
FROM (
SELECT COUNT(DISTINCT t1.Element) AS COUNT,
1 AS [sum]
FROM dbo.Table_1 AS t1
LEFT OUTER JOIN dbo.Table_1 AS t2
ON t1.Element = t2.Element
AND t1.[Group] <> t2.[Group]
GROUP BY
t1.[Group]
) AS result


select داخلی
ستون [COUNT]: تعداد اشتراکات برای هر گروه (مثلا a) براساس همه گروه ها به جز گروه فعلی، و المان های مشترک دیگر گروه ها با المان های گروه فعلی
ستون [Sum]: برای هر ردیف مقدار 1 برمی گرداند تا نخواهیم از دستور select برای بدست آوردن مجموع گروه ها استفاده کنیم : SELECT COUNT(DISTINCT [Group])
FROM Table_1
هزینه کوئری 36% به 64% خواهد بود!

و برای اینکه تعداد گروه ها (غیر تکراری) درست برگردانده شود از LEFT OUTER JOIN استفاده می کنیم.

در نهایت اگر باقیمانده تقسیم "مجموع اشتراکات" بر "تعداد گروه ها" برابر صفر شود همه با هم دارای اشتراک هستند در غیر این صورت پاسخ منفی خواهد بود.

تعداد گروه: 4
قابلیت اشتراک با : 1-4 گروه => 4*3 =12 حالت

[محمد سلیم آبادی]

دوست گرامی،
راه حلتون رو با داده های زیر امتحان کنید، متوجه خواهید شد که جواب Yes را میدهد در صورتی که بین دو مجموعه ی 1 و 2 اشتراکی وجود ندارد و این دو مجموعه مجزا هستند.

truncate table table_1
insert into table_1([group], element)
values (1,3),(1,5),
(2,4),(2,6),(2,7),
(3,4),(3,5),(3,8),
(4,3),(4,7),(4,8),(4,5);


تعداد گروه: 4
قابلیت اشتراک با : 1-4 گروه => 4*3 =12 حالت اینجا "ترکیبات" مطرح میشه نه "جایگشت" چرا که "A اشتراک B" با "B اشتراک A" فرقی ندارد. پس اگر تعداد گروه برابر با 4 باشد آنگاه تعداد ترکیبات ممکنه برابر است ترکیب 2 از 4 که برابر است با 6.

[cherchil_hra]

حرف شما صحیح است. برای مثال شما مقدار yes بر میگردونه که صحیح نیست.

اما اول منظورم رو واضح تر می گم و بعد کد اصلاح شده رو میذارم:

دوست گرامی،

اینجا "ترکیبات" مطرح میشه نه "جایگشت" چرا که "A اشتراک B" با "B اشتراک A" فرقی ندارد. پس اگر تعداد گروه برابر با 4 باشد آنگاه تعداد ترکیبات ممکنه برابر است ترکیب 2 از 4 که برابر است با 6.

1.نتیجه select داخلی میشه :
97092
گروه اول با 2 مجموعه(3 و 4)، گروه دوم با 2 مجموعه(3 و 4)، گروه سوم با 3 مجموعه (1و 2 و 4) و گروه چهارم با 3 مجموعه (1 و 2 و 3) ارتباط دارد که مجموع اینها می شود: 10
با توجه به اینکه هر مجموعه باید با n-1 مجموعه در ارتباط باشه3*4 = 12
(SUM([sum]) * (SUM([sum]) -1))
پس باید جواب منفی رو برگردونه چون 2 ارتباط کم داریم (که کد من اشتباه بود).
در واقع برای هر مجموعه، حاصل جمع تعداد ارتباطات آن، نه مجموع تعداد اشتراکات براساس عناصر، منظور بنده این بود.
بنابراین برای حساب صحیح، مجموعه های تکراری رو هم لازم داریم.

2. select داخلی هم برای مثال شما تعداد اشتباه برمی گردوند که اصلاح شد:


SELECT CASE SUM([Count])%((SUM([sum]) * (SUM([sum]) -1)))
WHEN 0 THEN 'Yes'
ELSE 'No'
END
FROM (
SELECT COUNT(g2) AS [Count],1 AS [SUM]
FROM (
SELECT t1.[group] AS g1,
t2.[group] AS g2
FROM dbo.Table_1 AS t1
LEFT OUTER JOIN dbo.Table_1 AS t2
ON t1.element = t2.element
AND t1.[group] <> t2.[group]
WHERE (NOT (t2.[group] IS NULL))
GROUP BY
t1.[group],
t2.[group]

) AS t
GROUP BY g1
) AS result

[محمد سلیم آبادی]

راه حل اصلاح شده خود را با داده های زیر تست کنید:

truncate table table_1
insert into table_1([group],element)
values (1,3),(1,5),(1,6),
(2,4),(2,6),(2,7),
(3,4),(3,5),(3,8),
(4,3),(4,7),(4,8),
(5,10),(5,11);

نتیجه خروجی کوئری شما برابر با Yes است. در صورتی که مجموعه شماره 5 کاملا مجزا از سایر مجموعه هاست.


گروه اول با 2 مجموعه(3 و 4)، گروه دوم با 2 مجموعه(3 و 4)، گروه سوم با 3 مجموعه (1و 2 و 4) و گروه چهارم با 3 مجموعه (1 و 2 و 3) ارتباط دارد که مجموع اینها می شود: 10
با توجه به اینکه هر مجموعه باید با n-1 مجموعه در ارتباط باشه3*4 = 12
الان متوجه منظورتون شدم. مثلا اگه سه مجموعه داشته باشیم، اون وقت برای برقراری اشتراک بین زوج مجموعه ها نیاز داریم هر مجموعه با دو مجموعه دیگه مرتبط باشه که تعداد ارتباطات برابر است با 2 + 2 + 2 که مساویست با 2 * 3 (یعنی تعداد مجموعه ها ضرب در تعداد مجموعه ها منهای یک).

[behrouzlo]

برای شروع محمد جان این کوئری را ببین که بر اساس پاسخ دوست قبلی هست
SELECT ( CASE WHEN SUM(P) = ( SELECT ( COUNT(DISTINCT [group]) - 1 )
* ( COUNT(DISTINCT [group]) )
FROM table_1
) THEN 'Yes'
ELSE 'No'
END ) Result
FROM ( SELECT T1.[group] ,
1 P
FROM dbo.table_1 T1
CROSS APPLY ( SELECT *
FROM dbo.table_1 T2
WHERE T1.[group] <> T2.[group]
AND T1.element = T2.element
) L
GROUP BY T1.[group] ,
L.[group]
) T

[محمد سلیم آبادی]

با استعانت از کوئری آقا بهروز و دوست خوبمون که اون تکنیک (n*n-1) رو مطرح کردن این کوئری حاصل شد.

SELECT ( CASE WHEN COUNT(*) = POWER((SELECT COUNT(DISTINCT [group]) FROM table_1), 2)
THEN 'Yes'
ELSE 'No'
END ) Result
FROM ( SELECT T1.[group]
FROM dbo.table_1 T1
INNER JOIN dbo.table_1 T2
ON T1.element = T2.element
GROUP BY T1.[group] ,
T2.[group]
) T

اگه در Self join شرط T1.element <> T2.element رو برداریم اون وقت می تونیم بگیم زمانی که تعداد سطرهای برگشتی (بعد گروه بندی بر اساس T1.group , T2.group) برابر باشه با تعداد مجموعه ها به توان دو (مثلا در سه مجموعه داریم: 3 + 3 + 3 = 3 * 3 = 3 به توان 2) مجموعه ها دو به دو دارای عنصر مشترک هستند.

استفاده از cross apply در اینجا کار مناسبی نیست همون join معمولی کفایت میکنه.

گرچه من هنوز یک راه حل خیلی ساده در چنته دارم که در انتها ارائه میدم.

[cherchil_hra]

اگه دستور where حذف بشه جواب درست میشه! :لبخند:


SELECT CASE SUM([Count])%((SUM([sum]) * (SUM([sum]) -1)))
WHEN 0 THEN 'Yes'
ELSE 'No'
END
FROM (
SELECT COUNT(g2) AS [Count],1 AS [SUM]
FROM (
SELECT t1.[group] AS g1,
t2.[group] AS g2
FROM dbo.Table_1 AS t1
LEFT OUTER JOIN dbo.Table_1 AS t2
ON t1.element = t2.element
AND t1.[group] <> t2.[group]

GROUP BY
t1.[group],
t2.[group]

) AS t
GROUP BY g1
) AS result

ممنون از اینکه کدها رو امتحان کردید و مشکلاتش رو گفتید، و البته اضافاتش رو حذف کردید !

[محمد سلیم آبادی]

من کوئری شما رو مطالعه کردم، واقعا تحسین برانگیزه، استفاده زیرکانه ای از left join صورت گرفته.
تونستم با کمی ریاضت اون رو ساده تر کنم (نیازی به عدد 1 برای شمارش سطرها و گروه بندی مجدد... نیست) توجه بفرمایید:


SELECT CASE COUNT(g2) % ((COUNT(DISTINCT g1) * (COUNT(DISTINCT g1) - 1)))
WHEN 0 THEN 'Yes'
ELSE 'No'
END
FROM (
SELECT t1.[group] AS g1,
t2.[group] AS g2
FROM dbo.Table_1 AS t1
LEFT OUTER JOIN dbo.Table_1 AS t2
ON t1.element = t2.element
AND t1.[group] <> t2.[group]
GROUP BY
t1.[group],
t2.[group]
) AS result

ضمنا همانطور که در پست قبلیم اشاره شد، جایگشت دو شی از n شی زمانی که تکرار مجاز باشد برابر است با n*n که مساویست با n به توان دو. پس ما میتونیم در قسمت case آنجایی که تعداد سطرها با هم مقایسه میشن برای کوتاهی کد از تکنیک فوق استفاده کنیم البته دیگه نباید شرط نابرابر بودن گروه ها بررسی شود. یعنی داریم:

SELECT CASE COUNT(g2) % POWER(COUNT(DISTINCT g1),2)
WHEN 0 THEN 'Yes'
ELSE 'No'
END
FROM (
SELECT t1.[group] AS g1,
t2.[group] AS g2
FROM dbo.Table_1 AS t1
LEFT OUTER JOIN dbo.Table_1 AS t2
ON t1.element = t2.element
GROUP BY
t1.[group],
t2.[group]
) AS result

[محمد سلیم آبادی]

روشی که با پشتوانۀ آن این مساله رو مطرح کردم به قرار زیر است:
"زمانی تمام مجموعه ها با هم دو به دو مشترک اند که وجود نداشته باشد مجموعه ای که با یکایک مجموعه ها مشترک نباشد"

به این گزاره که هم ارز هست با "به ازای هر مجموعه n-1 ارتباط مشترک با سایر مجموعه وجود دارد" اصطلاحا دو بار نقیض گیری گفته میشه. پس با پیاده سازی به زبان SQL خواهیم داشت:

select case
when not exists (select g1.[Group]
from dbo.Table_1 g1, dbo.Table_1 g2
where g1.Element = g2.Element
group by g1.[Group]
having count(distinct g2.[Group]) <
(select count(distinct [Group]) from dbo.Table_1))
then 'Yes'
else 'No'
End as result;

[behrouzlo]

محمد اگر امکانش هست کارایی این سه تا کوئری را با هم مقایسه کن و به مزایا و معایب هر کدام از کوئریها هم بپرداز

[محمد سلیم آبادی]

منظور از مقایسه دقیقا چیه؟ بهینه بودن از نظر زمان و فضای مصرفی؟
ای بابا سوادم به این حرفا قد نمیده چرا که تا حالا یک دقیقه هم آموزش ندیدم!:ناراحت:

به هر حال اگه بخواهیم راجب قابلیت "تعمیم" سخن به میان بیاریم میتونم بگم که کوئری زیر که در واقع "سه به سه مشترک بودن مجموعه" ها رو بررسی میکنه، از کیفیت بالایی برای تعمیم به مساله "n به n " برخودار هست.
بحث تعمیم پذیری رو نباید دست کم گرفت. یکی از فاکتور های ارزش گذاری به راه حل های ارائه داده شده در "مسابقات المپیاد ریاضی جهانی" همین تعمیم پذیری هست.


SELECT CASE WHEN COUNT(*) = POWER((SELECT COUNT(DISTINCT [group]) FROM table_1), 3)
THEN 'YES'
ELSE 'NO'
END
FROM
(
SELECT 1 c
FROM table_1 t1, table_1 t2, table_1 t3
WHERE t1.element = t2.element
AND t2.element = t3.element
GROUP BY t1.[group], t2.[group], t3.[group]
)d;