Kim jest idol w zbiorze?

Specyfikacja problemu:

Dane:

• n – liczba naturalna; liczba osób

• znajomosci – tablica o wymiarach n × n; przechowuje liczby naturalne 0 oraz 1; tablica informacji na temat tego, które osoby się znają

Wynik:

• komunikat wskazujący lidera zbioru lub informujący, że zbiór nie ma idola

Na przyjęciu znajduje się n osób. Osoby oznaczone są numerami od $0$ do $n-1$. Ponieważ jest to duża impreza, nie wszyscy goście się znają. Osoba A może znać osobę B, co niekoniecznie musi oznaczać, że osoba B zna osobę A. Może się okazać, że na przyjęciu pojawiła się osoba na tyle popularna, że jest znana przez wszystkich. Jeżeli ponadto okaże się, że osoba ta nie zna nikogo spośród pozostałych gości, możemy nazwać ją idolem.

Poniżej zaprezentowano dwuwymiarową tablicę typu logicznego, która określa stan znajomości wśród osób znajdujących się na przyjęciu. Jeżeli wartość znajomość[A][B] wynosi 1 (zauważmy, że to tablica liczb całkowitych, nie tablica boolowska), to przyjmujemy, że osoba A zna osobę B. Dla porządku przyjmujemy, że dana osoba nie zna siebie samej.

n ← 5
znajomość[n][n] ← [
	[ 0, 1, 0, 1, 1 ],
    [ 0, 0, 1, 0, 1 ],
    [ 0, 1, 0, 1, 1 ],
    [ 1, 1, 1, 0, 1 ],
    [ 0, 0, 0, 0, 0 ]
]

Zastanówmy się, ile pytań „Czy osoba A zna osobę B?” musimy zadać, aby sprawdzić, czy na przyjęciu pojawił się idol oraz kto nim jest.

Spróbujmy dokładnie przeanalizować informację, która wynika z odpowiedzi na pojedyncze pytanie: „Czy osoba A zna osobę B?” w kontekście wyszukiwania idola. Ponieważ idol jest osobą, która musi być znana przez każdego oraz sama nie może znać nikogo, wymienione wyżej pytanie pozwala nam stwierdzić, która z osób A lub B na pewno nie jest idolem. Jeżeli odpowiedź na nie brzmi twierdząco, wiemy, że osoba A nie może być idolem, ponieważ zna przynajmniej jedną osobę. Jeśli odpowiedź jest przecząca, to z kolei osoba B nie może być uznana za idola, ponieważ istnieje przynajmniej jedna osoba, która jej nie zna.

Tym sposobem możemy wyznaczyć idealnego kandydata na idola, zadając tylko $0$ do $n-1$ pytań. Zapiszmy ten proces w postaci pseudokodu:

n ← 5
znajomość[n][n] ← [
	[ 0, 1, 0, 1, 1 ],
    [ 0, 0, 1, 0, 1 ],
    [ 0, 1, 0, 1, 1 ],
    [ 1, 1, 1, 0, 1 ],
    [ 0, 0, 0, 0, 0 ]
]
kandydat ← 0

dla i = 1, 2, ..., n - 1 wykonuj
	jeżeli znajomość[kandydat][i] to
    	kandydat = i

Następnie sprawdzimy, czy wyznaczony kandydat może być idolem. W tym celu musimy przepytać wszystkich gości, czy znają wyznaczonego kandydata, a także przepytać kandydata, czy nie zna nikogo. Każdy z tych procesów będzie składał się z zadania $n-1$ pytań.

Do wcześniejszego pseudokodu dopiszemy linijki odpowiadające za sprawdzenie, czy wyznaczony kandydat jest idolem:

n ← 5
znajomość[n][n] ← [
	[ 0, 1, 0, 1, 1 ],
    [ 0, 0, 1, 0, 1 ],
    [ 0, 1, 0, 1, 1 ],
    [ 1, 1, 1, 0, 1 ],
    [ 0, 0, 0, 0, 0 ]
]

kandydat ← 0

dla i = 1, 2, ..., n - 1 wykonuj
	jeżeli znajomość[kandydat][i] to
    	kandydat ← i
    // w przeciwnym wypadku kandydat dalej może być idolem

// przepytaj gości, czy znają kandydata
dla i = 0, 1, ..., n - 1 wykonuj
	// sprawdź czy osoba i nie jest kandydatem
	jeżeli kandydat != i to
    	// sprawdź, czy osoba i zna kandydata
    	jeżeli !znajomość[i][kandydat] to
        	// osoba i nie zna kandydata
            // kandydat nie jest idolem
            // idol nie istnieje
        	wypisz "Idol nie istnieje"
            zakończ działanie pętli

// przepytaj kandydata, czy nie zna gości
dla i = 0, 1, ..., n - 1 wykonuj
	// sprawdź, czy kandydat nie jest osobą i
	jeżeli kandydat != i to
        // sprawdź, czy kandydat nie zna osoby i
    	jeżeli znajomość[kandydat][i] to
        	// kandydat zna osobę i
            // kandydat nie jest idolem
            // idol nie istnieje
        	wypisz "Idol nie istnieje"
            zakończ wykonywanie programu

wypisz "Idolem jest osoba numer " + kandydat

Powyższy kod można skrócić, wykorzystując podobieństwo dwóch pętli:

n ← 5
znajomość[n][n] ← [
	[ 0, 1, 0, 1, 1 ],
    [ 0, 0, 1, 0, 1 ],
    [ 0, 1, 0, 1, 1 ],
    [ 1, 1, 1, 0, 1 ],
    [ 0, 0, 0, 0, 0 ]
]

kandydat ← 0

dla i = 1, 2, ..., n - 1 wykonuj
	jeżeli znajomość[kandydat][i] to
    	kandydat ← i
    // w przeciwnym wypadku kandydat dalej może być idolem

// sprawdź, czy kandydat jest idolem
dla i = 0, 1, ..., n - 1 wykonuj
	// sprawdź czy nie pytamy kandydata o samego siebie
    // oraz czy czy osoba i zna kandydata
    // oraz czy kandydat nie zna osoby i
	jeżeli kandydat != i
    	oraz !znajomość[i][kandydat]
        oraz znajomość[kandydat][i] to
        // osoba i nie zna kandydata
        // lub kandydat zna osobę i
        // kandydat nie jest idolem
        // idol nie istnieje
        wypisz "Idol nie istnieje"
        zakończ wykonywanie programu

wypisz "Idolem jest osoba numer " + kandydat

Przedstawiony algorytm pozwala nam na znalezienie idola po zadaniu $3\left(n-1\right)$ pytań.

By to uzasadnić, przypomnijmy jak działa omówiony algorytm. Najpierw sprawdzamy, czy każda kolejna osoba (poza pierwszą) zna obecnego kandydata (czyli pierwszą osobę). Daje to $n-1$ pytań.

Następny krok wymaga sprawdzana, czy kolejne osoby z grupy znają kandydata (czyli znowu zadajemy $n-1$ pytań) oraz czy kandydat zna te kolejne osoby (kolejne $n-1$ pytań).

By znaleźć idola zadajemy $3\left(n-1\right)$ pytań. To oznacza, że złożoność czasowa omówionego algorytmu wynosi $O\left(n\right)$.

Implementacja algorytmu

To, czy dana osoba zna inną, przedstawimy za pomocą tzw. macierzy sąsiedztwa. Będzie to dwuwymiarowa tablica wypełniona zerami, jeżeli relacja znajomości z drugą osobą nie zachodzi, oraz jedynkami, jeżeli ta relacja zaistniała. Każdy wiersz tej macierzy będzie oznaczał stan wiedzy jednej osoby, zaś każda kolumna będzie oznaczała wiedzę o konkretnej osobie. Uznajemy, że żadna osoba nie zna samej siebie, dlatego przekątna tej tablicy będzie wypełniona zerami.

macierz = [
    [0, 1, 0, 1, 1],
    [0, 0, 1, 0, 1],
    [0, 1, 0, 1, 1],
    [1, 1, 1, 0, 1],
    [0, 0, 0, 0, 0]
]

Teraz zapiszemy pętlę, która przejdzie po wszystkich wierszach tej macierzy. W każdym jej wykonaniu będziemy sprawdzali, czy znaleźliśmy wiersz wypełniony samymi zerami – oznacza to, że mamy potencjalnego idola. Jeżeli okaże się, że dowolna inna osoba go nie zna, zbiór nie będzie miał innego idola.

macierz = [
    [0, 1, 0, 1, 1],
    [0, 0, 1, 0, 1],
    [0, 1, 0, 1, 1],
    [1, 1, 1, 0, 1],
    [0, 0, 0, 0, 0]
]

for i in range(len(macierz)):
    if macierz[i] == [0]*len(macierz):

Teraz stworzymy kolejną pętlę, która przejdzie po wszystkich elementach w kolumnie informującej nas o tym, czy osoba o indeksie i jest znana. Wyjątkiem będzie tutaj sam wiersz wypełniony zerami – zostanie on pominięty. Jeżeli znajdziemy tam jakiekolwiek zero, natychmiastowo stwierdzimy, że zbiór ten nie ma idola i zakończymy wykonywanie pętli.

macierz = [
    [0, 1, 0, 1, 1],
    [0, 0, 1, 0, 1],
    [0, 1, 0, 1, 1],
    [1, 1, 1, 0, 1],
    [0, 0, 0, 0, 0]
]

for i in range(len(macierz)):
    if macierz[i] == [0]*len(macierz):
        for x in macierz[:i] + macierz[i+1:]:
            if x[i] == 0:
                print("Zbior nie ma idola")
                break

Następnie, ponownie korzystając z konstrukcji for‑else, dodamy wyświetlanie informacji o znalezionym idolu. Jeżeli pętla przechodząca po wszystkich elementach w kolumnie wykona się bez wywołania instrukcji break, wtedy mamy pewność, że osoba o indeksie i jest idolem. Dodamy też instrukcję else na koniec pętli przechodzącej po wierszach – odpowiada to sytuacji, w której nie znaleźliśmy żadnej osoby nieznającej nikogo.

macierz = [
    [0, 1, 0, 1, 1],
    [0, 0, 1, 0, 1],
    [0, 1, 0, 1, 1],
    [1, 1, 1, 0, 1],
    [0, 0, 0, 0, 0]
]

for i in range(len(macierz)):
    if macierz[i] == [0]*len(macierz):
        for x in macierz[:i] + macierz[i+1:]:
            if x[i] == 0:
                print("Zbior nie ma idola")
                break
        else:
            print(f"Idol to {i}")
        break
else:
    print("Zbior nie ma idola")

Po uruchomieniu tego programu otrzymamy informację, że idolem jest osoba o numerze 4.

Przykładowe macierze, dla których idol nie istnieje:

macierz = [
    [0, 1, 0, 1, 1],
    [0, 0, 1, 0, 1],
    [0, 1, 0, 1, 1],
    [1, 1, 1, 0, 0],
    [0, 0, 0, 0, 0]
]

macierz = [
    [0, 1, 0, 1, 1],
    [0, 0, 1, 0, 1],
    [0, 1, 0, 1, 1],
    [1, 1, 1, 0, 0],
    [0, 0, 0, 1, 0]
]

Słownik