제약 조건이있는 3 개의 버킷으로 숫자 분할

Question

무작위로 생성 된 숫자를 3 개의 버킷으로 분할하는 좋은 알고리즘이 있으며 각 버킷에는 포함될 수있는 총량에 대한 제약이 있습니다.

예를 들어 임의로 생성 된 번호가 1,000이고 버킷 a, b 및 c로 분할해야한다고 가정합니다.

These ranges are only an example. See my edit for possible ranges. 
Bucket a may only be between 10% - 70% of the number (100 - 700) 
Bucket b may only be between 10% - 50% of the number (100 - 500) 
Bucket c may only be between 5% - 25% of the number (50 - 250) 
a + b + c must equal the randomly generated number 

당신은 그래서 그 비율 평균의 주위에있는 세 가지 버킷의 동등한 기회뿐만 아니라 버킷 C 등의 최대 타격 버킷 마찬가지로 동일한 기회가 완전히 무작위로 할당 된 양을 원한다.

편집 : 다음은 대부분 항상 사실 일 것입니다. a + b + c의 하단은 < 100 %, a + b + c> 100 %의 하이 엔드입니다. 이 백분율은 a, b 및 c의 허용 가능한 값을 나타 내기위한 것입니다. a가 10 %이고 b 및 c가 최대 값 (각각 50 % 및 25 %) 인 경우 합계가 100 %가 아니므로 숫자를 다시 지정해야합니다. 이것은 하나의 패스에서이 숫자를 할당하는 방법을 찾는 것으로 피하려고하는 정확한 사례입니다.

나는 한 번의 패스로이 숫자를 무작위로 선택하는 방법을 찾고 싶습니다.

Answer 1

업데이트 : 예, 맞습니다. 결과가 균일하게 배포되지 않습니다.

퍼센트 값이 자연수라고 가정 해 봅니다 (이 가정이 틀리면 더 이상 읽을 필요가 없습니다 :) 해결책이없는 경우). E = (p , P B, C, P )

는 3 개의 값 (각 버킷의 백분율)의 튜플 이벤트 e 정의하자. 다음으로 모든 가능한 이벤트를 작성하십시오. _n. 여기에있는 것은 개별적인 수의 이벤트로 구성된 튜플 공간입니다. 가능한 모든 사건이 발생할 가능성이 동일해야합니다.

우리는 함수 f (n) => e _n이 있다고 가정 해 봅시다. 그런 다음 임의의 숫자 n을 취하여 e 한 번에 e _n을 반환하면됩니다.

function f(n) { 
    int c = 0 
    for i in [10..70] { 
     for j in [10..50] { 
      for k in [5..25] { 
       if(i + j + k == 100) { 
        if(n == c) { 
         return (i, j, k) // found event! 
        } else { 
         c = c + 1 
        } 
       } 
      } 
     } 
    } 
} 

당신이 알고있는 것은 하나의 패스는 다음과 같습니다

이제 문제는 함수 의사 코드에서 f :

에게 (단지 그림에 대한) 매우 느린 방법을 만들 남아 해결책을 제시하지만 문제는 사라집니다. 함수 f는 매우 느립니다. 그러나 당신은 더 잘할 수 있습니다. 범위를 올바르게 설정하고 범위를 반복하는 대신 오프셋을 계산하면 모든 것을 조금 더 빠르게 계산할 수 있다고 생각합니다.

충분히 명확합니까?

---

먼저 범위를 조정해야합니다. 보유 할 상태 a+b+c = number을 얻을 수 없으므로 버킷의 10 %가 a이 아닙니다.

귀하의 질문에 관하여 : (1) 물통 a의 난수를 선택한 다음 (2) 물통 b의 범위를 최소 및 최대 백분율로 업데이트하십시오 (범위를 좁혀 야합니다). 그런 다음 (3) 버킷 b의 임의 번호를 선택합니다. 결국 c은 (4)의 조건을 만족해야 계산됩니다.

예 :

n = 1000 
(1) a = 40% 
(2) range b [35,50], because 40+35+25 = 100% 
(3) b = 45% 
(4) c = 100-40-45 = 15% 

또는 :

그것은 모든 이벤트가 균일하게 분포 여부를 확인하는 것입니다

n = 1000 
(1) a = 70% 
(2) range b [10,25], because 70+25+5 = 100% 
(3) b = 20% 
(4) c = 100-70-20 = 10% 

. 그 문제가 될해야하는 경우는 단계에서 범위 업데이트를 무작위로 할 수 있습니다 2.

Answer 2

문제는 (N = 3 귀하의 예제에서), 객체가 정의되고는 N 차원 객체의 임의의 지점을 선택하는 것과 같습니다 (검색 예에서) 식에 의해 :

명확 때문에 x 및 y 값을 따기 마지막 식 (*) 좌표 중 하나가 중복 즉 의

0.1 <= x <= 0.7 
0.1 <= y <= 0.5 
0.05 <= z <= 0.25 
x + y + z = 1 (*) 

는 Z를 지시한다.

제거 (*) 및 다른 방정식들 중 하나는 (N-1) 차원 상자, 예를 들어 우리 잎 (*)으로부터 유도한다 비항

0.05 <= (1 - x - y) <= 0.25 (**) 

및 Z에 대한 식에 의해 절단

0.1 <= x <= 0.7 
0.1 <= y <= 0.5 

. 이것은 기본적으로 상자를 통해 대각선 줄무늬입니다.

결과가 균일 해 지도록 (N-1) 차원 상자를 반복적으로 샘플링하고 (**) 충족하는 첫 번째 샘플링 지점을 받아들입니다. 단일 통과 솔루션은 편파 분포를 갖게 될 수 있습니다.