210. Computing a power set of a collection

נניח שיש לנו אוסף ואנחנו מעוניינים לחשב את אוסף האוספים החלקיים שלו (כאשר לא אכפת לנו מסדר, אלא רק מהאיברים שמופיעים בו).

ניתן לעשות זאת בצורה מעניינת בעזרת מספר Featureים של השפה:

public static IEnumerable<IEnumerable<T>> GetPowerSet<T>(IEnumerable<T> collection)
{
    if (!collection.Any())
    {
        // There is exactly one subset of the empty set,
        // the empty set itself.
        yield return Enumerable.Empty<T>();
    }
    else
    {
        // excluded will be the excluded item
        // of our set.
        // We now find the power set of all
        // elements except him.
        T excluded = collection.First();

        IEnumerable<T> withoutCurrent =
            collection.Skip(1);

        // Get the power set (using recursive call)
        IEnumerable<IEnumerable<T>> subsetsWithoutCurrent =
            GetPowerSet(withoutCurrent);

        // Iterate over the power set of the rest elements.
        foreach (IEnumerable<T> currentSet in subsetsWithoutCurrent)
        {
            // Each set yields two sets: one without the excluded
            // item and the second with the excluded item.
            IEnumerable<T> currentSetWithoutExcluded = currentSet;
            IEnumerable<T> currentSetWithExcluded = currentSet.Concat(new T[] {excluded});

            yield return currentSetWithoutExcluded;
            yield return currentSetWithExcluded;
        }
    }
}

מה קורה כאן? אם האוסף ריק, אנחנו מחזירים אוסף המכיל את התת קבוצה היחידה שיש – האוסף עצמו.

אם האוסף לא ריק, אנחנו מחשבים ברקורסיה את אוסף תת הקבוצות של כל האיברים פרט לאיבר הראשון.

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

זה די מזכיר את הקוד של הפרמוטציות (ראו גם טיפ מספר 172). הוספתי תיעוד כך שהקוד די מסביר את עצמו.

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

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

מומלץ לקרוא בויקיפדיה גם על משפט קנטור (יש שם הסבר אינטואיטיבי נחמד) ו האלכסון של קנטור.

סופ"ש חזק.