Lider w zbiorze

Liderem nazywamy liczbę, która w zbiorze liczącym $n$ elementów występuje więcej niż $\frac{n}{2}$ razy. Ponieważ inna liczba nie może występować w tym samym zbiorze liczbowym więcej niż $\frac{n}{2}$ razy, lider jest tylko jeden. W zbiorze {1, 4, 6, 1, 1} liderem jest liczba 1 – występuje w nim aż 3 razy.

Natomiast w zbiorze {8, 6, 4, 5, 3, 2} żadna z sześciu liczb nie jest liderem.

Właściwości zbiorów z liderem

Zbiory, które mają lidera, posiadają bardzo ważną właściwość: jeżeli z takiego zbioru usuniemy parę liczb – pod warunkiem, że będą one różne – zbiór ten nadal będzie miał tego samego lidera. Przeanalizujmy dwa przykłady:

• jeden, w którym obie usunięte liczby ze zbioru nie są liderem;

• drugi, w którym jedna z liczb jest liderem, natomiast druga nie.

Ze zbioru {1, 4, 6, 1, 1} usuwamy liczby 4 oraz 6 i zostajemy z podzbiorem {1, 1, 1}. Ponieważ zbiór ten składa się tylko z jedynek, bardzo łatwo stwierdzić, iż lider tego zbioru nie zmienił się i nadal jest nim liczba 1.

W drugim przypadku usuniemy jedną liczbę, która nie jest liderem, i jedną, która nim jest – usuniemy liczby: 4 oraz 1. Zostajemy wtedy ze zbiorem {1, 6, 1}, którego liderem nadal jest liczba 1.

Ponieważ para, która zostaje wyeliminowana, nie może składać się z tych samych liczb, przypadek, w którym usunięte zostaną dwie liczby lidera, nie zaistnieje.

Jeżeli weźmiemy jakikolwiek zbiór i będziemy odejmować od niego po dwa różne elementy, aż do momentu, w którym nie będziemy mogli usunąć już więcej, otrzymamy jeden z trzech możliwych rezultatów:

• pusty zbiór – oznacza, że zbiór nie ma lidera,

• zbiór z jednym elementem – jeżeli zbiór ma lidera, to będzie nim właśnie ten element, a jeżeli nie ma, to jest to po prostu element, który nie został usunięty; żeby upewnić się, czy ten element jest liderem, należy policzyć, ile razy wystąpił on w oryginalnym zbiorze i sprawdzić, czy liczba ta jest większa niż $\frac{n}{2}$,

• zbiór zawiera więcej niż jeden element, ale wszystkie pozostałe elementy mają takie same wartości – w tym przypadku element, który pozostał, na pewno jest liderem.

Algorytm wyszukiwania lidera

W e‑materiale teoretycznym poznaliśmy algorytm wyszukiwania lidera w zbiorze. Jego implementacja w języku Python wygląda następująco:

zbior = [1, 3, 1]
lider = zbior[0]
n = 1

for i in range(1,len(zbior)):
	if n > 0:
		if lider == zbior[i]:
			n = n + 1
		else:
			n = n - 1
	else:
		lider = zbior[i]
		n = 1
		
if n == 0:
	print("Zbiór nie ma lidera")
	exit()
    
liczba_wystapien_lidera = 0
for i in  range(0,len(zbior)):
	if zbior[i] == lider:
		liczba_wystapien_lidera += 1
    
if liczba_wystapien_lidera > len(zbior) / 2:
    print("Liderem zbioru jest ",lider)
else:
	print("Zbiór nie ma lidera")

Wyszukiwanie idola w zbiorze

Wyobraźmy sobie pewną grupę, w której każda osoba może, ale nie musi, znać pozostałe osoby. Ponieważ to, że osoba A zna osobę B, nie znaczy, że osoba B zna osobę A, może dojść do specyficznej sytuacji, w której odnajdziemy jedną osobę znaną przez wszystkich, jednocześnie nieznającą nikogo. Taką osobę nazywamy idolem.

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