הבלוג של גרי רשף

06/12/2010

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

Filed under: Uncategorized — תגיות: , , , — גרי רשף @ 07:41

לכל קבוצה בגודל n יש 2n תת קבוצות, למשל- לקבוצה {A,B,C} יש תת קבוצות {A},{B},{C},{A,B},{A,C},{B,C}; נוסיף להן את הקבוצה המקורית ואת הקבוצה הריקה ונקבל 8=23 תת קבוצות.
אם נבחר קבוצה בת 4 איברים- אפשר באותה שיטה למצוא את 16=24 תת הקבוצות שלה, או לעשות חשבון פשוט- לכל תת קבוצה של הקבוצה בת 3 האיברים ניתן להוסיף את האיבר הרביעי וניתן לא להוסיף; כלומר- מכל תת קבוצה של n=3 נקבל 2 תת קבוצות עבור n=4 ובסה"כ 16.

כך מוכיחים באופן כללי את הנוסחה באינדוקציה, וזה גם ישמש אותנו ליצור את תת הקבוצות בהמשך.
בנוסף כדאי לשים לב שאם נכתוב את כל המספרים מ-0 ועד ל-8 (לא כולל) באופן בינארי (בהתייחס לדוגמה הראשונה)- נקבל את כל תת הקבוצות, וזו דרך נוחה למספר או ליצור אותם. נניח – 5 נכתב בבינארית 101 וזה מייצג את תת הקבוצה עם האיבר הראשון והשלישי וללא השני.

למה זה שימושי? אני השתמשתי בשיטה הזו לפתרון בעיית סודוקו בעבר, אבל זו לא בעייה אמיתית מהחיים אלא תרגיל אינטלקטואלי מעניין לכל היותר; אבל אני יכול להיזכר בשתי בעיות שלפתרונן הייתי עשוי להידרש לפירוק קבוצה לכל תתי הקבוצות שלה:

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

2. יש לנו טבלה ואיננו יודעים מה המפתח שלה. משימה שבוודאי קרתה למי שהתבקש לטפל במערכות לא מתועדות שמי שהקים אותם כבר מזמן לא עובד בארגון, וגם מי שהחליף אותו ועשה איתו חפיפה לא נמצא; ובנוסף לכל- לא הוגדר מפתח באופן פורמלי למרות שמעשית אנחנו חושדים שיש כזה.. בדרך כלל נחפש עמודה בשם ID או TeudatZehut, אולי נצרף אליה עמודת תאריך שנמצאת בהתחלה וננסה לבדוק אם זה יוצר מפתח יחודי; אבל אם רוצים להיות שיטתיים- צריך לבדוק את כל תתי הקבוצות של עמודות הטבלה- החל מעמודות בודדות, המשך דרך צמדים של עמודות, עבור לשלישיות, וכלה בכל העמודות יחד; ולכל תת קבוצה כזו לבצע בדיקה האם היא יחודית (Unique), כלומר- האם Countו-Count Distinct מחזירים אותה תוצאה.

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

דיבורים דיבורים, אבל בלי קצת קוד זה לא זה- הרי מדובר בבלוג טכני בענייני SQL ולא במוסף ספרותי ברומו של עולם!

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

Declare        @N Int;

Set        @N=3;

With T As

(Select    1 N,

        Cast(Case When T2.N=1 Then '1' Else '' End As Varchar(Max))T

From    (Select    1 N

        Union All

        Select    2 N) T2

Union All

Select    T.N+1,

        T.T+Case When T2.N=1 Then Case When T.T='' Then '' Else ',' End+Cast(T.N+1 As Varchar) Else '' End T

From    T

Cross Join (Select    1 N

            Union All

            Select    2 N) T2

Where    T.N<@N)

Select    T

From    T

Where    T.N=@N

Order By T;

Go

הדרך השניה היא ליצור את כל המספרים מ-1 ועד 2n, ועבור כל אחד למצוא את החזקות של 2 שיוצרות אותו בעזרת האופרטור & (להלן- Bitwise And):

Declare    @N Int;

Set        @N=3;

With T As

(Select    0 N

Union All

Select    N+1

From    T

Where    N<Power(2,@N)-1)

Select    T1.N,

        T2.N+1

From    T T1

Left Join T T2

        On T2.N<=@N

        And T1.N & Power(2,T2.N)>0

Order By 1,2

בדרך השניה- השימוש ב-CTE הרקורסיבי נועד ליצור את המספרים, וניתן להחליף אותו בשליפה מטבלת מספרים- אם יש.

הדרך הראשונה החזירה לנו את הערכים משורשרים (נוח ויזואלית) והשניה את הערכים בצורת סט (נוח שימושית):

image

מודעות פרסומת

להגיב »

עדיין אין תגובות.

RSS feed for comments on this post. TrackBack URI

כתיבת תגובה

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

הלוגו של WordPress.com

אתה מגיב באמצעות חשבון WordPress.com שלך. לצאת מהמערכת / לשנות )

תמונת Twitter

אתה מגיב באמצעות חשבון Twitter שלך. לצאת מהמערכת / לשנות )

תמונת Facebook

אתה מגיב באמצעות חשבון Facebook שלך. לצאת מהמערכת / לשנות )

תמונת גוגל פלוס

אתה מגיב באמצעות חשבון Google+ שלך. לצאת מהמערכת / לשנות )

מתחבר ל-%s

בלוג בוורדפרס.קום.

%d בלוגרים אהבו את זה: