Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision | ||
lehrkraefte:blc:informatik:ffprg2-2020:dobble [2020/11/26 13:57] Ivo Blöchliger |
lehrkraefte:blc:informatik:ffprg2-2020:dobble [2020/12/11 15:43] (current) Ivo Blöchliger |
||
---|---|---|---|
Line 7: | Line 7: | ||
Dokumentieren Sie bitte Ihre Überlegungen und Codes. | Dokumentieren Sie bitte Ihre Überlegungen und Codes. | ||
+ | |||
+ | Es ist möglich, direkt mit Mengen zu arbeiten in Python: | ||
+ | <code python> | ||
+ | a = {1,2,3} | ||
+ | b = {2,3,4} | ||
+ | c = a.union(b) # Vereinigung | ||
+ | d = a.intersection(b) | ||
+ | |||
+ | s = len(d) | ||
+ | |||
+ | a.add(42) | ||
+ | |||
+ | b = b.copy() | ||
+ | </ | ||
+ | Siehe auch https:// | ||
<hidden Hilfestellungen> | <hidden Hilfestellungen> | ||
Line 27: | Line 42: | ||
Hier ist sehr anschaulich eine Methode beschrieben (mit dem 7x7-Quadrat von Symbolen), mit der sich komplette Sets erzeugen lassen, wenn $n-1$ prim ist. | Hier ist sehr anschaulich eine Methode beschrieben (mit dem 7x7-Quadrat von Symbolen), mit der sich komplette Sets erzeugen lassen, wenn $n-1$ prim ist. | ||
</ | </ | ||
+ | |||
+ | |||
+ | ====== Kartenset kompletieren ====== | ||
+ | |||
+ | <code python> | ||
+ | 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, | ||
+ | n = len(karten[0]) # Anzahl Symbole | ||
+ | if len(karte)==n: | ||
+ | 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, | ||
+ | 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(" | ||
+ | return karte|set([s for s in range(symbol, | ||
+ | |||
+ | |||
+ | |||
+ | 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, | ||
+ | print(karten) | ||
+ | |||
+ | for j in range(1,n): | ||
+ | while True: | ||
+ | print(" | ||
+ | r = complete(karten, | ||
+ | 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(" | ||
+ | r = complete(karten, | ||
+ | if r!=None: | ||
+ | karten.append(r) | ||
+ | print(r) | ||
+ | print(len(karten)) | ||
+ | |||
+ | """ | ||
+ | |||
+ | |||
+ | </ | ||
+ | |||