import random
from itertools import permutations, combinations

znanci = [
    ("Ana", "Ema"),
    ("Cilka", "Dani"),
    ("Cilka", "Ema"),
    ("Ana", "Dani"),
    ("Berta", "Dani")
]

otoki = {
    "Krk": {"Goli": 2, "Rab": 5, "Cres": 4},
    "Goli": {"Krk": 2, "Rab": 1, "Olib": 5, "Pag": 2},
    "Rab": {"Krk": 5, "Goli": 1, "Olib": 3, "Cres": 3},
    "Cres": {"Krk": 4, "Rab": 3, "Ist": 5},
    "Pag": {"Goli": 2, "Olib": 4, "Pašman": 5},
    "Olib": {"Rab": 3, "Goli": 5, "Pag": 4, "Iž": 4, "Dugi": 4, "Ist": 2},
    "Ist": {"Cres": 5, "Olib": 2, "Dugi": 1},
    "Pašman": {"Pag": 5, "Iž": 4, "Murter": 4},
    "Iž": {"Olib": 4, "Pašman": 4, "Dugi": 2},
    "Dugi": {"Ist": 1, "Olib": 4, "Iž": 2},
    "Murter": {"Pašman": 4}
}

imena = ["Ana", "Berta", "Cilka", "Dani", "Ema"]
random.shuffle(imena)

def je_pravilen(razpored):
    for oseba, kdo_ni in zip(razpored, znanci):
        if oseba in kdo_ni:
            return False
    return True

def je_urejen(razpored):
    return all(x < y for x, y in zip(razpored, razpored[1:]))

def je_pot_iz_krka_na_dugi(pot):
    return pot[0] == "Krk" and pot[-1] == "Dugi" and \
        all(y in otoki[x] for x, y in zip(pot, pot[1:]))

"""
print(je_pot_iz_krka_na_dugi(['Krk', 'Goli', 'Rab', 'Olib', 'Ist', 'Dugi']))
print(imena)
for k in range(2, len(otoki)):
    for izbor in combinations(otoki, k):
        for pot in permutations(izbor):
            if je_pot_iz_krka_na_dugi(pot):
                print(pot)
"""


zemljevid = [
    {0, 25, 21, 11},
    {1, 2, 3, 4, 22},
    {2, 1, 4, 5},
    {3, 1, 5, 6, 7},
    {4, 1, 2, 8, 9},
    {5, 2, 3, 10, 14},
    {6, 3, 7, 10},
    {7, 3, 6, 11},
    {8, 4, 9, 12},
    {9, 4, 8, 13},
    {10, 5, 6, 11},
    {11, 7, 10, 14, 0},
    {12, 8, 13, 16, 17},
    {13, 9, 12, 17},
    {14, 5, 11, 18, 19},
    {15, 16, 22},
    {16, 12, 15, 20},
    {17, 12, 13, 20, 21},
    {18, 14, 19, 21},
    {19, 14, 18, 21},
    {20, 16, 17, 23, 24},
    {21, 17, 18, 19, 23, 0},
    {22, 1, 15, 24},
    {23, 20, 21, 25},
    {24, 20, 22, 25},
    {25, 0, 23, 24}
    ]


def pokritje_pozresno():
    graf = sorted(enumerate(zemljevid), key=lambda x: -len(x[1]))
    nepokriti = set(range(len(zemljevid)))
    sladoledarji = []
    for stevilka, sosedi in graf:
        if sosedi & nepokriti:
            sladoledarji.append(stevilka)
            nepokriti -= sosedi
    return sladoledarji

def pokritje_pozresno2():
    nepokriti = set(range(len(zemljevid)))
    sladoledarji = []
    while nepokriti:
        stevilka, sosedi = max(enumerate(zemljevid), key=lambda x: len(x[1] & nepokriti))
        if sosedi & nepokriti:
            sladoledarji.append(stevilka)
            nepokriti -= sosedi
    return sladoledarji

s = pokritje_pozresno2()
print(s)
print(len(s))


def je_pokrito(sladoledarji):
    return all(sosedi & sladoledarji for sosedi in zemljevid)


krizisca = list(range(len(zemljevid)))
for k in range(6, 8):
    for izbor in combinations(krizisca, k):
        if je_pokrito(set(izbor)):
            print(izbor)