Geek asks and answers

Generating random integers with difference constraint

I have the following problem:

Generate M uniformly random integers in the range 0-N, wherein N → M, and wherein any one pair has less difference K. , where K → M .

At the moment, the best way I can come up with is to maintain a sorted list, then determine the lower bound of the current generated integer and test it with the lower and upper elements, if it is normal to insert an element between them.This is O complexity (nlogn).

Will there be a more efficient algorithm?

Example problem:

Generate 1000 uniformly random integers from zero to 100 million, where the difference between any two integers is at least 1000

A comprehensive way to solve this problem:

  • Define all n-select-m combinations that satisfy the constraint, call it set X
  • Choose a uniformly random integer i in the range [0, | X |).
  • As a result, select the i-th combination from X.

This solution is problematic when n-select-m is large, since listing and saving all possible combinations will be extremely costly. Therefore, the search for an effective online solution is required.

Note. The following is the implementation of the C ++ solution provided by pentadecagon

std::vector<int> generate_random(const int n, const int m, const int k)
{
   if ((n < m) || (m < k))
      return std::vector<int>();

   std::random_device source;
   std::mt19937 generator(source());
   std::uniform_int_distribution<> distribution(0, n - (m - 1) * k);

   std::vector<int> result_list;
   result_list.reserve(m);

   for (int i = 0; i < m; ++i)
   {
      result_list.push_back(distribution(generator));
   }

   std::sort(std::begin(result_list),std::end(result_list));

   for (int i = 0; i < m; ++i)
   {
      result_list[i] += (i * k);
   }

   return result_list;
}

http://ideone.com/KOeR4R

.

+3
source share
3 answers

EDIT: I adapted the text to require the creation of ordered sequences, each with the same probability.

a_i i=0..M-1 . .

b_i=a_i + i*(K-1)

b_i , a_i 1. , b [1..N], , a_i [1..N-(M-1)*(K-1)]. . , , . - O (M log M), . , , . Python :

import random
def random_list( N, M, K ):
    s = set()
    while len(s) < M:
        s.add( random.randint( 1, N-(M-1)*(K-1) ) )

    res = sorted( s )

    for i in range(M):
        res[i] += i * (K-1)

    return res
+3

-: , (M+1) - ( , , 0) N - (M-1)*K . .

:

M + 1 - composition

x i a M+1 - ( 0 ) ( , x i !).

solution set

m i :

construction composition to solution

, m i m + 1 K, m M N ( , ). , (M+1) -, , . ( , x M , , m i.)

, , , ; ,

solution set

- , . , , x i :

construction solution to composition

, -, x i 0, . , ( , x i 0) , :

enter image description here

, , m i.

, , N - (M-1)*K . , , - .

( ): N - (M-1)*K M M. (M+1) - N - (M-1)*K, M N - (M-1)*K + M, |. x 0 | , x M + 1 | , x i | i i+1. , , , M - [1; N - (M-1)*K + M] , , , Shuffle Fisher-Yates O(N + M log M) ( M ), M*K O(N) . , N , M, , , N.

. @DavidEisenstat , M - ; , .

, , , N ≥ (M-1) * K, 1 ( 0, ).

+2

:

for (int i = 0; i < M; ++i) {
  pick a random number between K and N/M
  add this number to (N/M)* i;

, N, K. O (n). .: -)

EDIT:

, " " K N/M, min(K, [K - (N/M * i - previous value)]). - K , .

EDIT:

, K N/M - 0 N/M. , , N/M * i, .

, , , , . , N/M * M N. ; .

. , , . , , " → ", , .. . , . - , M.

, , . , , . , .

EDIT:

, , , , . . , : ( N), :

int prevValue = 0;
int maxRange;
for (int i = 0; i < M; ++i) {
    maxRange = N - (((M - 1) - i) * K) - prevValue;
    int nextValue = random(0, maxRange);
    prevValue += nextValue;
    store previous value;
    prevValue += K;
}

, prevValue , . , , N, , .

, . , O (M) , , :

, . - , K . , , . 0, 1 2 , , . , , O (M), M , O (M ^ 2), , O (NlogN) N → M.

, OP:

  • 0- : [0... 100Mill], 1.0.
  • 1- : , .
    • , . 12345678, [0... 100Mill] [0... 12344678] [12346678... 100Mill]
    • , . 500, [0... 100Mill] [1500... 100Mill], [0... 500] . , 0, - , , , . ( 3 , .)
    • - , . 12344678/(12344678 + (100Mill - 12346678)) (100Mill - 12346678)/(12344678 + (100Mill - 12346678))

: 0 1 , . .

, , O (M), M N. .

, !

+1

More articles:


All Articles