content top
יצירת כל תתי הקבוצות לקבוצה נתונה

יצירת כל תתי הקבוצות לקבוצה נתונה

הפוסט הזה נכתב בעקבות בעייה אמיתית, אבל כדי לפשט ולהקל אתמקד בעניין העקרוני ולא המעשי.
נתונה קבוצת המספרים 1..N, ואנחנו מעוניינים לקבל את כל תתי הקבוצות שלה.

ל-N מספרים יש (2 בחזקת N) תתי קבוצות. למשל: לקבוצה {1,2} יש 2^2=4 תתי קבוצות: {},{1},{2},{1,2}, והן כוללות גם את הקבוצה הריקה {} וגם את הקבוצה המקורית כולה – הקבוצה האוניברסלית – {1,2}.
למה (2 בחזקת N) תתי קבוצות? כי כל איבר יכול להיות בקבוצה ויכול לא להיות (=2 אפשרויות), ולכן יש לכפול את 2 בעצמו כמספר האיברים הקבוצה.
אציג להלן 2 דרכים שונות להתמודד עם המשימה.
הדרך הראשונה מחוללת את (2 בחזקת N) המספרים, וליצוג הבינארי של כל אחד מהם מתאימה את תת הקבוצה שלו. במקרה של N=2 ניצור את ארבעת המספרים 0-3 בבינארית: 00,01,10,11; ואם הספרה השמאלית מייצגת את המספר 1 והימנית את 2, אנחנו מקבלים את 4 תתי הקבוצות, החל מהקבוצה הריקה 00 וכלה בקבוצה האוניברסלית 11. ברור שאם N=5 אזי יש ליצור את 32 המספרים מ-0 (המיוצג בבינארית על ידי 00000) וכלה ב-31 (המיוצג על ידי 11111).
לשם כך ניצור 2 אובייקטים:

  1. משתנה טבלה שיכיל את המספרים מ-1 ועד N.
  2. טבלת מספרים מ-0 ועד (2 בחזקת N). אני בדרך כלל נעזר ב-CTE רקורסיבי שמחולל את המספרים, פחות יעיל, אך יותר בטוח (גם ללא טבלת מספרים מוכנה והעדר הרשאות ניתן להשתמש בו).

לכל מספר מסעיף 2 אשרשר למחרוזת את המספרים המתאימים מסעיף 1. השירשור יתבצע בעזרת XML (טריק מוכר שלא ארחיב לגביו), ואבחר את המספרים המתאימים בעזרת האופרטור & המכונה Bitwise And שגם לגביו לא ארחיב, אך הוא בודק האם חזקה מסויימת של 2 כלולה בייצוג הבינארי של המספר.

Declare    @N1 Int=20;

Declare @Tn Table(n Int Primary Key);

With Nm1 As

(Select    1 n

Union All

Select    n+1

From    Nm1

Where    n<@N1)

Insert

Into    @Tn

Select    *

From    Nm1;

Declare    @N2 Int=Power(2,@N1);

With Nm2 As

(Select    0 n

Union All

Select    n+1

From    Nm2

Where    n<@N2-1)

Select  Nm2.n,

        OA.Script

From    Nm2

Outer Apply (Select    (Stuff((Select Concat(',',Nm1.n)

                    From    @Tn Nm1

                    Where    Nm2.n & Power(2,Nm1.n-1)>0

                    Order By Nm1.n

                    For XML Path('')),1,1,'')) Script) OA

Option    (MaxRecursion 0);

בחלקו העליון של הסקריפט משתנה הטבלה ואיכלוסו,

מתחתיו ה-CTE הרקורסיבי מ-0 ועד 2 בחזקת 20 (נריץ על N=20 כדי “לטחון” קצת את המערכת),

וב-Outer Apply מופיע השימוש ב-& והשירשור בעזרת XML.

להלן 10 השורות הראשונות בפלט:

image

ליד המספר 9 משורשרים 1,4 כי (2 בחזקת 0) ועוד (2 בחזקת 3) הם 9. כמובן החסרתי 1 מ-1,4 כדי לקבל את 0,3 בהתאמה.

ליד המספר האחרון בפלט – 1048575, נקבל את השירשור של כל המספרים מ-1 ועד 20 כי (2 בחזקת 0) ועוד (2 בחזקת 1) ועוד .. ועוד (2 בחזקת 19) זה 1048575 או (2 בחזקת 20) פחות 1, למי שמחפש דרכי קיצור..

הדרך השנייה מתבססת על המכפלה ב-2 שתוארה בתחילת הפוסט, המציינת את העובדה שכל איבר נוסף בקבוצה מכפיל פי 2 את מספר תתי הקבוצות. ניתן להוכיח שלקבוצה בת N איברים יש (2 בחזקת N) תתי קבוצות באינדוקציה מתימטית המתבססת על זה, אבל לא כאן..

בכל מקרה: עבור N=20 ניצור קבוצה ריקה (סט של שורה אחת ובה Null), ובעזרת CTE רקורסיבי ניצור Join בינה לבין סט הכולל 2 שורות – 1 ו-Null, ושוב סט של 2 שורות – 2 ו-Null, וכך הלאה עד 20. בכל אחת מ-20 האיטרציות – מספר השורות בסט יוכפל, פעם ישורשר הערך הנוכחי ופעם לא:

Declare    @N1 Int=20;

Declare @Tn Table(n Int Primary Key);

With Nm2 As

(Select    0 N,

        Cast(Null As Varchar(Max)) Script

Union All

Select    Nm2.N+1 N,

        Cast(Concat(Nm2.Script,','+Cast(Nm1.N*(Nm2.N+1) As Varchar(Max))) As Varchar(Max)) T

From    Nm2

Cross Join (Select    Null N

            Union All

            Select    1 N) Nm1

Where    Nm2.N<@N1)

Select    Stuff(Script,1,1,'') Script

From    Nm2

Where    N=@N1

Option    (MaxRecursion 0);

שימו לב לתנאי בשורה לפני האחרונה: N=@N1: הסט שנוצר כולל את כל הסטים לכל ערכי N מ-1 ועד 20, אבל אותנו מעניין רק זה של 20. ניתן כמובן לקבל באותו מחיר את כל האחרים. אם נכתוב בתנאי N=2 נקבל את 4 השורות שתוארו בהתחלה.

מבחינת היעילות יש פער מסויים אך לא משמעותי בין שני הפתרונות.

מי שהביצועים מדירים שינה מעיניו במקרה זה, כדאי שיעזר בטבלת מספרים במקום ב-CTE רקורסיבי (לפחות לגבי הפתרון הראשון).


כתיבת תגובה

האימייל לא יוצג באתר. (*) שדות חובה מסומנים

one × 4 =