נתונה קבוצת איברים שכולם שונים זה מזה.
המשימה היא לכתוב אלגוריתם שמחזיר את כל תתי הקבוצות האפשריות.
אני אתחיל מדוגמא קטנה כדי להיזכר בכל סוגי תתי הקבוצות שיש –
A = {1,2,3} subsets = {{},{1},{2},{3},{1,2},{2,3},{1,3},{123}}
סבבה, מהדוגמא שלי אני יכולה לראות את כל תתי הקבוצות שאני צריכה לייצר – הקבוצה הריקה, הקבוצה המלאה, כל תתי הקבוצות שמכילות בדיוק איבר אחד מהקבוצה, כל תתי הקבוצות שמכילות בדיוק שני איברים מהקבוצה וכן הלאה…
סבבה, עכשיו – איך אני פותרת את השאלה באופן הנאיבי ביותר?
פתרון נאיבי אחד יהיה לעבור על הקבוצה מספר פעמים, וכל פעם לחפש את הגודל הבא של קבוצות שאפשר ליצור. כך –
def get_all_subsets(A):
subsets = set()
for i in range(0,len(A)):
subsets.append(get_all_subsets_of_size_k(A,k))
return subsets
השלב הבא הוא לממש את הפונקציה שמקבלת קבוצה וגודל מסוים מוצאת את כל תתי הקבוצות באותו הגודל.
איך עושים את זה?
בהינתן גודל k אנחנו צריכים לבחור בכל פעם k איברים שונים מהקבוצה A. אין לי מושג איך עושים את זה, אבל אני יכולה אולי לנסות להקביל את הבעיה הזו לבעיה דומה וקצת קלה יותר.
נשתמש באותה הדוגמא כמו למעלה, והפעם נסמן כל תת קבוצה בסדרה של ביטים. כאשר ביט 1 אומר שלקחנו את האיבר וביט 0 אומר שלא לקחנו את האיבר.
A = {1,2,3} k=0 subsets={{000}} k=1 subsets={{100}{010}{001}} k=2 subsets={{110}{101}{011}} k=3 subsets={{111}}
מה אפשר לראות מהדוגמא הזו? שבהינתן k התת קבוצות שקיבלנו הן כל המספרים הבינאריים מ-0 עד 2(len(A שקיימים בהם בדיוק k ביטים דלוקים.
אז כדי לפתור את הבעיה של מציאת כל תתי הקבוצות אני יכולה לרוץ בלולאה על כל המספרים הבינאריים וכל אחד מהם ייצג תת קבוצה לפי מיקום הביטים הדלוקים בו.
אני אכתוב את האלגוריתם הזה.
def get_all_subsets(A):
subsets = set()
max_num = pow(2,len(A))
for i in range(0,max_num):
current_subset = set()
bin_repr = bin(i)
for j in range(0,len(bin_repr)):
if bin_repr[j] == 1:
current_subset.add(A[j])
subsets.add(current_subset)
return subsets
עכשיו אני אריץ דוגמא לראות שהאלגוריתם שלי באמת עובד.
A = {1,2,3} subsets = {} max_num = pow(2,3)=8 i=0 current_subset={} bin_repr=0 j=0 subsets={{}} i=1 current_subset={} bin_repr=1 j=0 current_subset={1} subsets={{},{1}} i=2 current_subset={} bin_repr=10 j=0 current_subset={1} . . .
מממ… אוקי, הנה באג קטן. כיוון שלא ריפדתי את המספר הבינארי שלי אלא לקחתי אותו כמו שהוא הספרה הראשונה ב-1 וב-10 היא זהה, ולכן בעבור שניהם ילקח האיבר הראשון בקבוצה.
כרגע אני לא רוצה לבזבז זמן על ההתעסקות עם זה, כי אני יודעת שזה פשוט, אז אני אניח שכתבתי פונקציה שנקראת get_padded_bin שמחזירה לי את התוצאה המתאימה מרופדת בגודל (len(A (פתרון אחר היה יכול להיות פשוט לרוץ מימין לשמאל במקום משמאל לימין).
def get_all_subsets(A):
subsets = set()
max_num = pow(2,len(A))
for i in range(0,max_num):
current_subset = set()
bin_repr = get_padded_bin(i,len(A))
for j in range(0,len(bin_repr)):
if bin_repr[j] == 1:
current_subset.add(A[j])
subsets.add(current_subset)
return subsets
אני ארוץ על הדוגמא מחדש –
A = {1,2,3} subsets = {} max_num = pow(2,3)=8 i=0 current_subset={} bin_repr=0 j=0 subsets={{}} i=1 current_subset={} bin_repr=001 j=0 j=1 j=2 current_subset={3} subsets={{},{3}} i=2 current_subset={} bin_repr=010 j=0 j=1 current_subset={2} j=2 subsets={{},{3},{2}} i=3 current_subset={} bin_repr=011 j=0 j=1 current_subset={2} j=2 current_subset={2,3} subsets={{},{3},{2},{2,3}} i=4 bin_repr=100 . . subsets={{},{3},{2},{2,3},{1}} i=5 bin_repr=101 . . subsets={{},{3},{2},{2,3},{1},{1,3}} i=6 bin_repr=110 . . subsets={{},{3},{2},{2,3},{1},{1,3},{1,2}} i=7 bin_repr=111 . . subsets={{},{3},{2},{2,3},{1},{1,3},{1,2},{1,2,3}}
מעולה, הפתרון עובד והוא נראה טוב. פשוט ואלגנטי.
מה הסיבוכיות שלו?
בהינתן קבוצה A בגודל m אנחנו רצים 2m פעמים… אאוץ’.
אבל רגע… נכון, זו סיבוכיות נוראית. האבל האם אפשר בכלל לשפר אותה?
נניח והייתה לי קבוצה A בגודל m וכבר היו נותנים לי את קבוצת החזקה ורק הייתי צריכה להדפיס אותה. מה הייתה הסיבוכיות? הגודל של קבוצת חזקה היא 2m. רק ההדפסה הייתה נעשית בסיבוכיות מעריכית.
כן חשוב לציין עכשיו את הלולאה הפנימית בגודל m שהופכת את הסיבוכיות המלאה של האלגוריתם ל-(O(2m+1 כי בגדלים האלה זה משמעותי.
יאי! עבודה טובה.
קוד מלא בגיט – https://github.com/mgershovitz/maya_solves/blob/master/power_set.py
פתרון יותר פשוט: בהסתכלות על היצוג הבינארי של המספרים מ 0 עד 1 כמספר האיברים בקבוצה (אם למשל יש חמישה איברים – עד 11111), כל מספר בתחום הזה, ביצוג בינארי, אומר איזה איברים מהקבוצה לקחת. למשל 13=1101 – אומר לקחת את האיברים הראשון השלישי והרביעי. כך כל מספר נותן תת-קבוצה אחרת, וכל האפשרויות מכוסותץ
קודם כל, בלוג נהדר תודה לך!!!
יש גם פתרון רקורסיבי נחמד:
JavaScript:
var subsetsOfSize = (a, size, index = 0, curr = [], res = []) => {
if (curr.length >= size) {
res.push([…curr]);
return res;
}
for (let i = index; i < a.length; i++) {
curr.push(a[i]);
subsetsOfSize(a, size, i + 1, curr, res);
curr.pop();
}
return res;
};
var allSubsets = (a) => {
if (!a) return [];
const res = [];
for (let i = 0; i <= a.length; i++) {
const sets = subsetsOfSize(a, i);
res.push(sets);
}
return res;
};