Dobble ist ein Kartenspiel, wo auf jeder Karte genau $n=8$ unterschiedliche Symbole abgebildet sind. Die Symbole auf der Karte sind so gewählt, dass bei jedem beliebigen Paar von Karten es immer genau ein Symbol gibt, in dem die Karten übereinstimmen. Im Spiel geht es darum, das gemeinsame Symbol vor den Mitspielern zu finden.

Schreiben Sie ein Programm, das ein Dobble-Kartenset erzeugt. Anstatt $m$ verschiedene Symbole werden einfach Zahlen $0, \ldots, m-1$ verwendet, eine Karte wird als Array mit 8 Einträgen betrachtet. Z.B. [0,1,2,3,4,5,6,7].

Das Programm sollte das grösst-mögliche Kartenset erzeugen und wenn möglich auch für andere $n$ (Anzahl Symbole auf einer Karte) funktionieren.

Dokumentieren Sie bitte Ihre Überlegungen und Codes.

Es ist möglich, direkt mit Mengen zu arbeiten in Python:

a = {1,2,3}
b = {2,3,4}
c = a.union(b) # Vereinigung
d = a.intersection(b)  # Schnittmenge
 
s = len(d)  # Anzahl Elemente
 
a.add(42)  # Anfügen eines Elements, modifiziert die Menge a
 
b = b.copy()  # Kopie der Menge b

Siehe auch https://www.w3schools.com/python/python_sets_methods.asp

from functools import reduce
 
# Voraussetzungen: 
# karten ist ein Array mit mindestens einer Karte
# Bei mehreren Karten bildet das Array ein valides Kartendeck, d.h.
# jedes Kartenpaar hat genau 1 gemeinsames Element.
#
# Die Symbole sind ganze Zahlen, startend bei 0
# 
# karte ist eine evtl. unvollständige Karte, die mit jedem Element aus
# karten höchstens 1 gemeinsames Element hat.
#
# Die Funktion liefert entweder None, wenn die Karte unmöglich
# vervollständigt werden kann, oder die lexikografisch erste
# vervollständigte Karte.
 
def complete(karten, karte):
    n = len(karten[0]) # Anzahl Symbole
    if len(karte)==n:  # Test ob vollständige Karte auch gültig
        if all(len(k & karte)==1 for k in karten):
            return karte
        else:
            return None
 
    # Symbole, die nicht zusätzlich auf die Karte dürfen
    forbidden = karte.copy()
    for k in karten:
        if (len(k & karte)==1):
            forbidden|=k
 
    # Symbole, von denen mindestens eins auf die Karte muss
    possibles = set()
    hasZero = False
    for k in karten:
        if (len(k & karte)==0):
            hasZero = True
            # Karte ohne gemeinsame Symbole, aber alle verboten, also unmöglich
            if len(k.difference(forbidden))==0:
                return None
            possibles |= k.difference(forbidden)
    possibles = list(possibles)
    if hasZero:
        possibles.sort()
        for p in possibles:
            r = complete(karten, karte | {p})
            if r!=None:
                return r
        # Es gibt karten ohne gemeinsames Element und es unmöglich eines davon hinzuzufügen
        return None
 
    # Alle Karten haben jetzt genau ein gemeinsames Element, also entsprechend neue Symbole hinzufügen
    symbol = max(reduce(lambda a,b: a|b, karten, set()))+1
    print("Nächstes Symbol ist %d" % symbol)
    return karte|set([s for s in range(symbol, symbol+n-len(karte))])
 
 
 
n = 8
total = n*n-n+1
karte = set([i for i in range(n)])
print(karte)
karten = [karte]
for i in range(n-1):
    karten.append(complete(karten,{0}))
print(karten)
 
for j in range(1,n):
    while True:
        print("Try %d" % j)
        r = complete(karten,{j})
        if r!=None:
            karten.append(r)
            print(r)
        else:
            break
print(karten)
print(len(karten))
"""            
for i in range(2):
    for s in range(total):
        print("Starting with Symbol %d" % s)
        r = complete(karten,{s})
        if r!=None:
            karten.append(r)
            print(r)
            print(len(karten))
 
"""