특정 속성을 만족하는 임의의 배열 요소를 선택하십시오.

StackOverflow https://stackoverflow.com/questions/966108

문제

다음과 같은 목록이 있다고 가정해 보겠습니다. elements, 각각은 일부 부울 속성을 만족하거나 만족하지 않습니다. p.만족하는 요소 중 하나를 선택하고 싶습니다. p 균일한 분포로 무작위로.이 속성을 만족하는 항목이 몇 개나 되는지 미리 알 수 없습니다. p.

다음 코드가 이를 수행합니까?:

pickRandElement(elements, p)
     randElement = null
     count = 0
     foreach element in elements
          if (p(element))
               count = count + 1
               if (randInt(count) == 0)
                    randElement = element

     return randElement

(randInt(n) 임의의 int를 반환합니다. k ~와 함께 0 <= k < n.)

도움이 되었습니까?

해결책

수학적으로 작동합니다. 유도에 의해 입증 될 수 있습니다.

n = 1 요소에 대해 명확하게 작동합니다. p.

n+1 요소의 경우 확률 1/(n+1)의 요소 n+1을 선택하므로 확률은 정상입니다. 그러나 이것이 이전 N 요소 중 하나를 선택할 수있는 최종 확률에 어떤 영향을 미칩니 까?

각각의 이전 n은 요소 n+1을 찾을 때까지 확률 1/n으로 선택 될 가능성이있었습니다. 이제 n+1을 찾은 후, 요소 n+1이 선택 될 가능성이 1/(n+1)가 있으므로, 이전에 선택한 요소가 선택된 상태로 유지 될 가능성이 있습니다. 이는 N+1 발견 후 선택된 최종 확률이 1/N * (N/N+1) = 1/N+1이라는 것을 의미합니다. 이는 균일 분포를 위해 모든 N+1 요소에 대해 원하는 확률입니다.

N = 1에서 작동하고 N+1에서 작동하면 N+1에서 작동하면 모든 n에서 작동합니다.

다른 팁

네, 그렇다고 믿습니다.

일치하는 요소를 처음 만나면 반드시 선택합니다.다음번에는 1/2의 확률로 새 값을 선택하므로 두 요소 각각의 확률은 동일합니다.다음에는 1/3의 확률로 새 값을 선택하고 다른 요소도 1/2 * 2/3 = 1/3의 확률로 남겨 둡니다.

이 전략에 대한 Wikipedia 기사를 찾으려고 노력하고 있지만 지금까지는 실패했습니다...

보다 일반적으로는 길이를 알 수 없는 시퀀스에서 무작위 샘플을 선택하는 것입니다.시퀀스는 초기 시퀀스를 가져와 필터링하여 생성되지만 알고리즘에는 해당 부분이 전혀 필요하지 않습니다.

이 작업을 수행하기 위해 MoreLINQ에 LINQ 연산자가 있다고 생각했는데 저장소에서 찾을 수 없습니다.편집하다:다행히도 아직까지 남아있습니다. 이 답변:

public static T RandomElement<T>(this IEnumerable<T> source,
                                 Random rng)
{
    T current = default(T);
    int count = 0;
    foreach (T element in source)
    {
        count++;
        if (rng.Next(count) == 0)
        {
            current = element;
        }            
    }
    if (count == 0)
    {
        throw new InvalidOperationException("Sequence was empty");
    }
    return current;
}

~ 안에 프로그래밍 연습, pg. 70, (Markov 체인 알고리즘) 이에 대한 비슷한 알고리즘이 있습니다.

[...]
  nmatch = 0;
  for ( /* iterate list */ )
    if (rand() % ++nmatch == 0) /* prob = 1/nmatch */
      w = suf->word;
[...]

"항목이 몇 개 있는지 모르면 임의로 하나의 항목을 선택하기위한 알고리즘을 확인하십시오. 변수 Nmatch는 목록이 스캔 될 때 일치 수를 계산합니다. 표현식 표현식. 

rand() % ++nmatch == 0

nmatch를 증가시키고 확률 1/nmatch에 따라 충실합니다. "

DeCowboy는 이것이 작동한다는 좋은 증거를 가지고 있습니다 상단 코더

명확성을 위해 다음을 시도합니다.

pickRandElement(elements, p)
     OrderedCollection coll = new OrderedCollection
     foreach element in elements
          if (p(element))
               coll.add(element)
     if (coll.size == 0) return null
     else return coll.get(randInt(coll.size))

나에게는 이것이 당신이 하려는 일이 무엇인지 훨씬 더 명확하게 만들고 자체 문서화하는 것입니다.게다가 더 간단하고 우아하며, 이제 각 항목이 고르게 분포되어 선택된다는 것이 분명해졌습니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top