Zdobądź losowy element w połączonej liście jednokierunkowej za pomocą jednego przesunięcia czasowego

Question

Mam listę połączoną w jednym kierunku, nie znając jej rozmiaru.

Chcę uzyskać losowy element na tej liście, a ja po prostu mam jednorazowo szansę na przejrzenie listy. (Nie mam uprawnień do przechodzenia przez dwa lub więcej razy)

Jaki jest algorytm dla tego problemu? Dzięki!

Answer 1

To tylko reservoir sampling ze zbiornikiem o rozmiarze 1.

Zasadniczo jest to naprawdę proste

1. Odbiór pierwszego elementu niezależnie (na liście o długości 1, pierwszy element jest zawsze próbka).
2. Dla każdego innego elementu z prawdopodobieństwem 1/n gdzie n jest liczbą obserwowanych do tej pory elementów, zastępujemy już wybrany element bieżącym elementem, na którym się znajdujesz.

Jest to próbka jednolicie, ponieważ prawdopodobieństwo wybrania dowolnego elementu na koniec dnia wynosi 1/n (ćwiczenie do czytnika).

Answer 2

Jest to prawdopodobnie pytanie do wywiadu. Próbnik rezerwuaru jest używany przez naukowca danych do przechowywania odpowiednich danych w ograniczonym magazynie z dużego strumienia danych.

Jeśli zbieranie elementów k z tablicy z N elementów, tak, że prawdopodobieństwo każdego elementu pobierane powinny być takie same (K/N), należy wykonać dwa etapy,

1) przechowuje pierwsze elementy k w magazynie. 2) Kiedy następny element (k + 1) pochodzi ze strumienia, oczywiście nie masz już miejsca w kolekcji. Generuj losową liczbę od o do n, jeśli wygenerowana losowa liczba jest mniejsza niż k przypisz l, zastąp pamięć [ l] z elementem (k + 1) ze strumienia.

Teraz powracając do pytania, tutaj rozmiar pamięci to 1. Tak, wybierz pierwszy węzeł, powtórz na liście drugi element. Teraz wygeneruj losową liczbę, jeśli jej 1, zostaw próbkę samodzielnie, w przeciwnym razie zmień element pamięci z listy

Answer 3

To pytanie może zostać wykonane przy użyciu próbkowania zbiorczego. Opiera się na wybieraniu losowych elementów z n pozycji, ale tutaj n może być bardzo duże (co nie musi pasować do pamięci!) I (jak w twoim przypadku) nieznane początkowo.

Wikipedii ma zrozumiały algorytm, który cytuję poniżej:

array R[k]; // result 
integer i, j; 

// fill the reservoir array 
for each i in 1 to k do 
    R[i] := S[i] 
done; 

// replace elements with gradually decreasing probability 
for each i in k+1 to length(S) do 
    j := random(1, i); // important: inclusive range 
    if j <= k then 
     R[j] := S[i] 
    fi 
done 

pytanie wymaga tylko 1 więc bierzemy wartość k = 1.

C realizacja:

https://ideone.com/txnsas