טבלת מספרים: חישובים קומבינטוריים

05/07/2015

תגיות: , ,
אין תגובות

החבר’ה מתקשרים אלי הביתה: “גרי, עזוב אותך מ-Azure ומ-Extended Events ומכל השטויות האלו, ופנק אותנו באיזה פוסט שימושי על קומבינטוריקה!”. כשמבקשים ממני יפה – אינני מסרב..
(ומי שלא הבין: להלן פוסט בלתי שימושי בעליל שאני כותב כי נחמד להתעסק עם נושאים כאלו, ומזל שיש לי בלוג – בדיוק בשיל זה)

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

With    T_Nm As

(Select    1 N

Union All

Select    N+1 N

From    T_Nm

Where    N<100)

Select    *

Into    T_Nm

From    T_Nm;

Go

 

Alter Table T_Nm Alter Column N Int Not Null;

Go

 

Alter Table T_Nm Add Constraint PK_T_Nm Primary Key Clustered(N);

Go

מי שלא רוצה ליצור טבלה – יכול להשתמש ישירות ב-CTE בכל שליפה: פחות יעיל, אבל לא מחייב הרשאות מיוחדות ולא נותרות שאריות בסוף..
נתחיל עם חישובי פרמוטציות, ובעברית תמורות: מספר האפשרויות לסידור N אובייקטים שונים הוא !N. למשל- את הספרות 1,2,3 אפשר לסדר ב-6=!3 סידורים שונים: 123, 132, 213, 231, 312, 321.
ב-TSQL אין פונקציית אגרגציה המחשבת מכפלה, ולכן כדי לחשב את !N בעזרת טבלת המספרים נשתמש בטריק ישן נושן הכולל שימוש בלוגריתמים: נסכום את הלוגריתמים של המספרים מ-1 עד N, ולסכום נחשב אנטי-לוג.

Declare    @N Int=3;

Select    Exp(Sum(Log(N))) Permutations

From    T_Nm

Where    N<=@N;

image

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

הלאה- נעבור לקומבינציות, ובעברית – צירופים: כמה אפשרויות יש לקבל 5 הטלות מטבע בהן 2 פעמים H ו-3 פעמים T?
HHTTT,HTHTT,HTTHT,HTTTH,THHTT,THTHT,THTTH,TTHHT,TTHTH,TTTHH ובסה”כ 10 אפשרויות.
מה הנימוק המתימטי? יש !5 אפשרויות לסדר 5 מטבעות, שזה 120; ברם: יש לחלק בכל התמורות הפנימיות של H (שזה !2=2)  ובכל התמורות הפנימיות של T (שזה !3=6), ובסה”כ 10=120/2/6.
כך גם לגבי השאלה כמה אפשרויות יש להוליד 5 ילדים שמתוכם 3 בנות ו-2 בנים,
או לחלק 5 תיקים בין שתי מפלגות כך שמפלגה T תקבל 3 תיקים ומפלגה H 2 תיקים;
ובעברית- image (קרי: N מעל M). אפשר כמובן לחשב בנפרד את !N, את !M ואת !(N-M); ולבסף לחלק את הראשון בשני האחרים; אבל כדי לעבור על הטבלה רק פעם אחת ותוך כדי כך לקזז ערכים, נחשב כך:

Declare    @M Int=5,

        @N Int=2;

Select    Exp(Sum(Log(N)

        -Iif(N<=@N,Log(N),0)

        -Iif(N<=@M-@N,Log(N),0))) Combinations

From    T_Nm

Where    N<=@M;

image

הוסף תגובה
facebook linkedin twitter email

כתיבת תגובה

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