조합 객체의 총 수를 무작위로 선택하는 것과 관련된 정리가 있습니까?

Question

일반적인 알고리즘 챌린지는 특정 종류의 물체를 균일하게 무작위로 생성하는 것입니다. 예를 들어, $ k $ 의 $ n $ 문자, 이 질문 .

나는 그러한 작업을 해결할 때, 재발 관계를 통해 이러한 조합 물체를 계산하는 의 알고리즘 임의의 알고리즘을 알고리즘으로 변형시킬 수 있다는 것을 알아 차렸다. 조합 물체. 내 질문은이 기술의 이름이 있습니까? 이것이 사실이 될 때 말하는 정리가 있습니까?

예를 들어 $ n $ $ 1 $ s 및 $ 0 $ s, 2 개의 인접한 $ 1 $ s. 나는 $ a [n] $ 이 그러한 서열의 수가 되라고부터 시작할 수 있습니다. $$ [n]= A [N-1] + A [N-2]. $$

(이것은 Fibonacci 관계입니다.) 이를 통해 $ a [i] $ $ i= 1 $ 에 효율적으로 계산할 수 있습니다. $ i= n $ . 이제는 무작위로 이러한 순서를 생성하고 싶다면 다음과 같아야합니다.

1 단계 : $ 1 $ $ r $ 을 생성합니다. > $ a [n] $ .

2 단계 : 재발성 관계를 사용하여 $ r $ th 시퀀스에 해당하는 하위 용어를 찾습니다.

$ r \ le a [n-1] $ , 재귀 적으로 $ r $ < / span> $ a [n-1] $ 에 의해 계산되고 $ 0 $ 을 추가합니다.

그렇지 않으면 $ a [n-1] $ r '= r - a [n-1] $ , $ r'$ $ a [n-2] $ 에 의해 계산되고 $ 01 $ 을 추가하십시오.

여기서 일어나는 것은 $ a [n] $ 에 대한 재발성 관계가 있으며,이를 반환하는 재귀 알고리즘으로 변환 할 수 있다는 것입니다. $ R $ th $ a [n] $ . 나는 이것이 잘 알려져 있다고 가정하고 있으므로, 이에 대한 참조 나 고전적인 결과에 관심이 있습니다. 특히 이것은 예제 $ a [n] $ 에만 적용되지만, 재발성 관계를 만족시키는 에 대해서는 사실이어야합니다. 속성.

또한, 나는 이것이 무작위 테스트에 대한 연구에 대한 연구와 관련 될 수 있다고 생각합니다.

Answer 1

이들은 순위 및 불안정한 기능 라고합니다.알고리즘 계산 및 불안정한 알고리즘을위한 재발성 관계 간의 통신에 대해 옳습니다.