בקבוצה נתונה.

השאלה שלי היא כזאת : יש לבנות אלגוריתם המייצר את כל תתי הקבוצות שבקבוצה הנתונה.

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

001

010

100

110

101

011

111

אם עד כאן אני צודק , אז בעצם השאלה שלי היא בגדול איך כותבים קוד כזה?

תודה..

קודם כל, את הקבוצה הריקה מייצגים ע"י 000.

תחשוב על זה שייצגת כאן את כל אחת מתתי הקבוצות ע"י מספר בעל 3 ספרות בינאריות. מספר בעל 3 ספרות בינאריות הוא פשוט מספר בין 0 ל-7. לכן, הדרך הכי פשוטה לעבור על כל תתי הקבוצות של קבוצה בגודל n הוא:

for (int i = 0 ; i < (1 << n) ; i++)

בכל איטרציה i מייצג את האיברים שנמצאים בקבוצה. איבר כלשהו נמצא בקבוצה אם הביט המתאים לו ב-i הוא 1. בשביל לבדוק איזה ביטים דולקים צריך להשתמש בפעולות הבינאריות & ו-|.

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

נכון, אבל זה הרבה יותר מסובך

^ ומאוד מאוד לא יעיל, כשמדובר ב-n גדול.