길이가 n 이하인 균일하게 무작위 인 문자열 선택?

Question

길이가 n 인 모든 문자열에서 균일하게 임의의 문자열을 선택한다고 가정 해 봅시다 (문자 A - Z와 같이 문자열을 만들 수있는 고정 된 문자 집합이 있다고 가정 해 봅시다). 문자열의 길이를 미리 알았다면 무작위로 문자열의 각 문자를 균등하게 선택하여 임의의 문자열을 쉽게 선택할 수있었습니다. 그러나 무작위로 문자열을 일정하게 선택하기 위해서는 무작위 길이를 고르고 그 길이의 무작위 문자열을 선택할 수는 없습니다. 왜냐하면 완전히 임의의 문자열을 선택하는 것이 짧은 것보다 긴 문자열이 있기 때문에 짧은 것보다 긴 길이.

무작위로 균일하게 대부분에서 길이의 문자열을 선택 N에 대한 알려진 알고리즘이 있습니까?

감사합니다. 각 문자가 있습니다

Answer 1

26 자이며 길이는 최대 n입니다.그래서 문자열의 총 수는 다음과 같습니다

P(string s is chosen) = 1/TotalNumStrings 

지금 당신이 임의의 길이를 선택하고 선택의 제안 전략을 고려

Total Number of Strings = \sum_{i=1}^n 26^i 

우리가 동일한 확률로 선택되어야한다 이들 각각 필요 그 길이의 무작위 문자열. 베이 즈 규칙에 따라 우리는 :

P(string s being chosen which has length i) = 
    P(string s being chosen | string has length i) * 
    P(we want a string of length i) = (1/26^i) * (1/n) = 1/(26^i * n) 

이 1/TotalNumStrings와 같지 않습니다. 당신은 이미 이것이 작동하지 않을 것이라는 것을 알고 있었지만 올바른 선택 전략에 동기를 부여했습니다. 다음

지금 캐릭터를 선택

P(string s being chosen which has length i) = 
    P(string s being chosen | string has length i) * 
    P(we want a string of length i) = 
     1/(26^i) * P(chosen string has length i) = 1/NumStrings. 

을 따라서 우리가 P = 26^I/NumStrings (선택한 문자열 길이를 갖는 I)! 타다.

따라서 선택 전략을 요약하면 다음과 같습니다. 우선 길이 i를 확률 26^i/NumStrings로 선택하십시오. 그런 다음 해당 범주에서 임의의 문자열을 선택하십시오.

Answer 2

가능한 문자 수의 다른 요소를 추가, 그래서 그렇게 26 일 문자 문자열, 26 × 26 두 글자 문자열 및이있다. 따라서 크기를 임의로 늘리면됩니다.

예. 당신은 대부분의 308,915,776에서 임의의 숫자를 선택하고 다음과 같이 문자열 길이를 선택할 수 있습니다

< 26  - 1 
< 702  - 2 
< 15576  - 3 
< 456976 - 4 
< 11881376 - 5 
< 308915776 - 6 

숫자는하지만, 조금 큰 빠르게 틱을 얻을, 즉 N가 작은 당신만큼 작동 할 수 있도록. 그렇지 않으면 부동 소수점 숫자를 사용하고 0과 1 사이의 범위를 대신 사용할 수 있습니다.

Answer 3

문자 세트의 크기가 주어진 길이의 분포를 계산할 수 없습니까?

k는 문자열 k보다 짧은 길이의 문자열에 대한 길이의 비율을 결정한다. 이것은 다음에서 유래합니다 : wikipedia.

그래서, 최대한의 문자열을 가정 한 후 무작위로 짧은 문자열의 상대적 기회를 결정합니다.

짧은 반복 볼 수있는 경우 n-1 이하의 경우.

이 접근법은 반올림 오류를 합리적으로 처리한다고 생각합니다. n이 적당한 크기 일 때 실제로 짧은 문자열을 얻을 확률은 여전히 ​​매우 작지만 대표적입니다.

이 금액을하려면, 우리는 원하는 :

k^n samples of length n 
k^(n-1) of length n-1 
etc. 
k of length 1 
1 of length 0 

p(length < x)/p(length <= x) 
= sum(1+..+k^x-1)/sum(1+..+k^x) 
= (1 - k^-x)/ (k-k^-x) 

그래서 우리는 다음과 같이 구현할 수 있습니다

int getLength(int n, int setSize) 
{ 
    if (n == 0) 
     return 0; 
    double oneOverKtoTheN = pow(1.0/setSize, (double)n); 
    double pLengthN = (1-oneOverKtoTheN)/(setSize - oneOverKtoTheN); 
    double sample = ((double) rand())/RAND_MAX; 
    if (sample < pLengthN) 
     return n; 
    return getLength(n-1, setSize); 
} 

oneOverKtoTheN 인해 시작하는 부동 소수점까지 하락하지만, 같은 n 할 수있는 방법을 참고 감소해야한다.

Answer 4

균일 무작위 문자열 길이를 뺀 길이가 X mod (n + 1)과 같습니다. 여기서 X는 범위 [0, 무한대]와 성공 확률 1/k 및 k가있는 기하학입니다. 알파벳의 문자 수. 문자열을 무작위로 무작위로 선택하고 bignum을 사용하지 않고 다음을 수행합니다. 기하학적 mod (n + 1)을 샘플링합니다 (예 : A가 아닌 문자까지 샘플링하여 비 A로 생성 된 mod n + 1)). 길이 n에서 해당 값을 뺀 문자열을 생성합니다.

Answer 5

다소 큰 문자열이 필요한 경우 27 번째 문자가 문자열 끝 문자 인 곳에서 각 문자열을 무작위로 27 개 문자로 작성하는 것입니다. 최대 허용 n보다 긴 문자열은 거부해야하지만 세대가 상당히 효율적이어야합니다. 그래서의 범위 공의 '올바른'유통 및 길이 임의의 문자열을 생산하는 N 다음의보다 효율적인 버전을 사용할 수 있습니다 길이 n까지 모든 문자열의

Function RandomString(n : integer) : string; 
var 
    RandomChar : char; 
begin 
    result := ''; 
    repeat 
    RandomChar := Char('a' + Random(27)); 
    if RandomChar in ['a'..'z'] then 
     result := result + RandomChar; 
    if Length(result) > n then 
     result := ''; 
    until RandomChar not in ['a'..'z']; 
end; 

Answer 6

번호 (26^(n+1)-1)/(26-1)입니다.

아이디어는 문자열이 비어 있는지 결정하는 것입니다. 확률은 (26-1)/(26^(n+1)-1)입니다. 그러한 확률의 이벤트를 생성하기 위해 우리는 26^(n+1) 이벤트를 생성하고, 그 중 하나를 무시하고 나머지 이벤트를 25 개 선택합니다.

char GenerateRandomCharacter() 
{ 
    ... 
} 
std::string GenerateRandomStringOfFixedLength(int length) 
{ 
    std::string result; 
    for(int c=0;c<length;++c) 
     result.push_back(c); 
    return result; 
} 
bool WillWeGenerateEmptyString(int maxLength) 
{ 
    while(true) 
    { 
     const std::string sample=GenerateRandomStringOfFixedLength(maxLength+1); 
     if(sample==std::string(maxLength+1,'A')) 
      continue;//this leaves 26^n-1 values 
     else 
      return sample.substr(1)==std::string(maxLength,'A');//only 25 strings satisfy this 
    } 
} 
std::string Generate(int maxLength) 
{ 
    if(WillWeGenerateEmptyString(maxLength)) 
     return std::string(); 
    else 
    { 
     std::string result; 
     result.push_back(GenerateRandomCharacter()); 
     result+=Generate(maxLength-1); 
     return result; 
    } 
}