288. Computing all topologies of a finite set

שבוע מתמטי טוב
Equality, LINQ, Math, Math Puzzles

במתמטיקה קיים מושג שנקרא טופולוגיה:

מדובר באוסף קבוצות ביחס לקבוצה X עם התכונות הבאות:

  1. הקבוצה הריקה והקבוצה X שייכות לטופולוגיה
  2. איחוד (כלשהו) של קבוצות מהטופולוגיה שייך לטופולוגיה
  3. חיתוך (סופי) של קבוצות מהטופולוגיה שייך לטופולוגיה.

שאלה לא טריוואלית לשאול היא כמה טופולוגיות אפשר ליצור מעל קבוצה סופית בעלת מספר נתון של איברים?

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

זה נראה כך:

1
2
3
4
5
6
7
8
public static IEnumerable<IEnumerable<IEnumerable<T>>> Topologies<T>(IEnumerable<T> world)
{
    IEnumerable<IEnumerable<T>> discreteTopology = GetPowerSet(world);
    IEnumerable<IEnumerable<IEnumerable<T>>> candidates = GetPowerSet(discreteTopology);
    return candidates.Where(x => IsTopology(x, world));
}

מה שקורה כאן זה שעוברים על כל התת קבוצות של התת קבוצות של X. זאת מאחר וטופולוגיה מורכבת מתתי קבוצות שלX, ולכן כל הטופולוגיות האפשריות הן תתי קבוצות של תתי קבוצות של X. (השתמשתי פה במימוש של תתי קבוצות מטיפ מספר 210)

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static bool IsTopology<T>(IEnumerable<IEnumerable<T>> candidate, IEnumerable<T> world)
{
    SetComparer<T> comparer = new SetComparer<T>();
    if (!candidate.Contains(Enumerable.Empty<T>(), comparer) ||
        !candidate.Contains(world, comparer))
    {
        return false;
    }
    var pairs =
        from first in candidate
        from second in candidate
        select new {first, second};
    return pairs.All(x =>
        candidate.Contains(x.first.Union(x.second), comparer) &&
        candidate.Contains(x.first.Intersect(x.second), comparer));
}

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

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

1
2
3
4
5
6
7
8
9
10
11
12
public class SetComparer<T> : IEqualityComparer<IEnumerable<T>>
{
    public bool Equals(IEnumerable<T> x,IEnumerable<T> y)
    {
        return new HashSet<T>(x).SetEquals(y);
    }
    public int GetHashCode(IEnumerable<T> obj)
    {
        return 0;
    }
}

שימו לב שהמימוש לא הכי אידאלי, אבל זה המימוש הכי פשוט אפשר לכתוב.

כעת נוכל להריץ את הקוד ולראות מספר טופולוגיות:

על הקבוצה הריקה נקבל את הטופולוגיות הבאות:

$ \{\{\}\} $

על קבוצה עם איבר בודד נקבל את:

$ \{\{\},\{0\}\} $

על קבוצה עם שני איברים נקבל 4 אפשרויות:

$ \{\{\},\{0,1\}\} \\ \{\{\},\{1\},\{0,1\}\} \\ \{\{\},\{0\},\{0,1\}\} \\ \{\{\},\{1\},\{0\},\{0,1\}\}$

על קבוצה עם 3 איברים נקבל 29 אפשרויות:

$ \{\{\},\{0,1,2\}\} \\ \{\{\},\{2\},\{0,1,2\}\} \\ \{\{\},\{1\},\{0,1,2\}\} \\ \{\{\},\{1,2\},\{0,1,2\}\} \\ \{\{\},\{2\},\{1,2\},\{0,1,2\}\} \\ \{\{\},\{1\},\{1,2\},\{0,1,2\}\} \\ \{\{\},\{2\},\{1\},\{1,2\},\{0,1,2\}\} \\ \{\{\},\{0\},\{0,1,2\}\} \\ \{\{\},\{1,2\},\{0\},\{0,1,2\}\} \\ \{\{\},\{0,2\},\{0,1,2\}\} \\ \{\{\},\{2\},\{0,2\},\{0,1,2\}\} \\ \{\{\},\{1\},\{0,2\},\{0,1,2\}\} \\ \{\{\},\{2\},\{1,2\},\{0,2\},\{0,1,2\}\} \\ \{\{\},\{2\},\{1\},\{1,2\},\{0,2\},\{0,1,2\}\} \\ \{\{\},\{0\},\{0,2\},\{0,1,2\}\} \\ \{\{\},\{2\},\{0\},\{0,2\},\{0,1,2\}\} \\ \{\{\},\{2\},\{1,2\},\{0\},\{0,2\},\{0,1,2\}\} \\ \{\{\},\{0,1\},\{0,1,2\}\} \\ \{\{\},\{2\},\{0,1\},\{0,1,2\}\} \\ \{\{\},\{1\},\{0,1\},\{0,1,2\}\} \\ \{\{\},\{1\},\{1,2\},\{0,1\},\{0,1,2\}\} \\ \{\{\},\{2\},\{1\},\{1,2\},\{0,1\},\{0,1,2\}\} \\ \{\{\},\{0\},\{0,1\},\{0,1,2\}\} \\ \{\{\},\{1\},\{0\},\{0,1\},\{0,1,2\}\} \\ \{\{\},\{1\},\{1,2\},\{0\},\{0,1\},\{0,1,2\}\} \\ \{\{\},\{0\},\{0,2\},\{0,1\},\{0,1,2\}\} \\ \{\{\},\{2\},\{0\},\{0,2\},\{0,1\},\{0,1,2\}\} \\ \{\{\},\{1\},\{0\},\{0,2\},\{0,1\},\{0,1,2\}\} \\ \{\{\},\{2\},\{1\},\{1,2\},\{0\},\{0,2\},\{0,1\},\{0,1,2\}\} $

על קבוצה עם 4 איברים נקבל 355 אפשרויות.

אם נסתכל על הסדרה של מספר האיברים, היא הולכת

$ 1,1,4,29,355, \dots $

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

מה שכן, ניתן לשאול מספר שאלות מעניינות בנושא.

אפשר לשפר את הקוד שכתבתי, למרות שהוא מדגים שימוש במספר Featureים של השפה והFramework.

יום טופולוגי טוב!

שתף