한 번에 한 방향으로 링크 된 목록의 무작위 요소를 가져옵니다.

Question

크기가 모르게 단일 방향 연결 목록이 있습니다.

이 목록에서 무작위 요소를 가져오고 싶습니다. 한 번만 기회가 있습니다. (두 번 이상 통과 할 수 없음)

이 문제의 알고리즘은 무엇입니까? 감사!

Answer 1

이 1.

본질적으로는

1. 에 관계없이 첫 번째 요소를 선택 정말 간단 단지 reservoir sampling 크기의 저수지이다 (길이 1의 목록은, 첫 번째 요소는 항상 샘플입니다).
2. 확률 1/n (여기서 n은 지금까지 관찰 된 요소의 수임)의 모든 다른 요소에 대해 이미 선택된 요소를 현재 현재 요소로 바꿉니다.

하루가 끝날 때 요소를 선택하는 확률이 1/n (독자에게 운동)이기 때문에 균일하게 표본 추출됩니다.

Answer 2

이것은 아마도 인터뷰 질문 일 것입니다. 저장소의 샘플링은 데이터 과학자가 대량의 데이터 스트림에서 관련 데이터를 제한된 저장 공간에 저장하는 데 사용됩니다.

하면, N 요소와 임의의 어레이에서 K 개의 요소를 수집 할 경우되도록하면 동일한 (K/N)이어야 수집 각 요소는 두 단계,

1) 제 K 요소 스토어 따라 확률 저장 장치에. 2) 다음 요소 (k + 1)가 스트림에서 오는 경우 분명히 더 이상 컬렉션에 공간이 없습니다. 생성 된 임의의 숫자가 k보다 작 으면 o부터 n까지 임의의 숫자를 생성하고 저장 장치 [ l]을 (k + 1) 엘리먼트와 비교한다.

이제 질문에 대한 답은 여기 저장 크기는 1입니다. 그러면 첫 번째 노드를 선택하고 두 번째 요소에 대한 목록을 반복합니다. 이제 임의의 숫자를 생성하고 1이면 샘플을 그대로 둡니다. 목록에서 저장 요소

Answer 3

이 질문은 저장소 샘플링을 사용하여 수행 할 수 있습니다. 그것은 n 개의 항목 중에서 k 개의 임의 항목을 선택하는 것을 기반으로 합니다만, 여기 n은 매우 커서 (메모리에 맞지 않아도됩니다!), 처음에는 알려지지 않았을 수도 있습니다. 우리는 K = (1)를 취할 수 있도록

가

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 

문제는 단지 하나의 값을 필요

는 위키 제가 아래 인용 이해할 알고리즘을 갖는다.

C 구현 :

https://ideone.com/txnsas