This series is my summary of data structure and algorithm when I was looking for a job many years ago. There are basic parts and classic interview questions of various companies. It was first published on CSDN. Is sorted out for a series of friends in need of reference, if there is a mistake, welcome to correct. The full code address for this series is here.
0 overview
Random algorithms involve a lot of probability theory knowledge, sometimes it is difficult to watch the derivation process carefully, of course, it is good to fully understand the derivation process, if not understand the derivation process, at least remember the conclusion is necessary. This article summarizes some of the most common random algorithms, which I wrote a few years ago when I was looking for a job. It should be noted that the random function randInt(a, b) assumes that it can randomly produce integers in the range [a,b], i.e., each integer is equally likely to be produced (although this is not always possible in practice, but don’t worry too much about it, a lot of things in this world are random). The code for this article is here.
1 Arrange arrays randomly
Given an array A that contains elements 1 through N, our goal is to construct A uniform random arrangement of the array.
A common approach is to assign each element of an array A[I] A random priority P[I], and then sort the array by that priority. For example, if our array is A ={1, 2, 3, 4}, if the selected priority group is P ={36, 3, 97, 19}, then we can get the sequence B={2, 4, 1, 3}, because 3 has the highest priority (97), and 2 has the lowest priority (3). This algorithm needs to generate a sequence of precedence series, and it also needs to sort the array using the sequence of precedence series, which I won’t describe in detail here, but there’s a better way to get a randomly arranged array.
A better way to generate randomly arranged arrays is to “in-place” a given array, which can be done in O(N) time. The pseudocode is as follows:
RANDOMIZE-IN-PLACE ( A , n )
forI please 1 to ndoSwap A[I] ↔ [RANDOM(I, n)]Copy the codeAs shown in the code, at iteration I, element A[I] is randomly selected from element A[I…n], and after iteration I, we never change A[I] again.
The probability that A[I] is at any position j is 1/n. This is easy to derive, for example, that the probability of A[1] being at position 1 is 1/n, which is obvious, because the probability of A[1] not being replaced by an element from 1 to n is 1/n, and then it doesn’t change A[1] anymore. And the probability that A[1] is at position 2 is also 1/n, because A[1] must be at position 2 at the first time with A[k] (k=2… The probability of the first exchange with A[k] is (n-1)/n, while the probability of the second substitution is 1/(n-1), so the total probability is (n-1)/n * 1/(n-1) = 1/n. You can do the same thing for other cases.
Of course, this condition can only be A necessary condition for random arrays, that is, the probability that A[I] is at position j with A probability of 1/n does not necessarily mean that it can produce random arrays. Because the number of possible permutations is less than n! Although the probability is equal, the number of permutations does not meet the requirement. There is a counter example of this in the introduction to algorithms.
The algorithm randomize-in-place can generate uniform random permutation, and its proof process is as follows:
Firstly, the concept of k permutation is given. The so-called K permutation is the permutation of k elements selected from n elements, so it has n! /(n-k)! K permutations.
Loop invariant: Before iteration I of the for loop, for each possible i-1 permutation, the probability that subarray A[1…i-1] contains the i-1 permutation is(n-i+1)! / n!.
-
Initialization: before the first iteration, I =1, then the loop invariant means that for each permutation of 0, the probability that subarray A[1…i-1] contains that permutation is (n-1+1)! / n! = 1. A[1…0] is an empty array with zero elements, so the probability that A contains all possible zeros is 1. The invariant holds.
-
Maintain: Assume that the probability of the array’s i-1 permutation occurring in A[1…i-1] is (n-i+1)! / n! , then after iteration I, the probability of all I permutations of the array appearing in A[1… I] is (n-i)! / n! . Here’s how to derive this conclusion:
- Consider a special permutation of I p = {x1, x2. xi}, it is arranged by an I -1 p’ ={x1, x2… , xI – 1} followed by an xiComposition. Set two event variables E1 and E2:
-
E1 is the event in which the algorithm places the permutation P ‘to A[1…i-1], and the probability is Pr(E1) = (n-i+1)! / n! .
-
E2 is the event that puts XI into A[I] at iteration I. So we get the I arranged in the probability of A [1… I] is Pr studying E1} {E2 = Pr Pr {E1} {E2 | E1}. And Pr | E1} {E2 = 1 / (n – I + 1), so studying E1} {E2 Pr = {E2 | E1} {E1} Pr Pr = 1 / (n – I + 1) * (n – I + 1)! / n! = (n − I)! / n! .
-
End: I =n+1 at the end, so it follows that A[1…n] is A given permutation of n with A probability of 1/n! .
C implementation code is as follows:
void randomInPlace(int a[], int n)
{
int i;
for(i = 0; i < n; i++) { int rand = randInt(i, n-1); swapInt(a, i, rand); }}Copy the codeextension
If the above random permutation algorithm is written as follows, can it also produce uniform random permutation?
PERMUTE-WITH-ALL( A , n )
forI please 1 to ndoSwap A[I] ↔ [RANDOM(1, n)]Copy the codeNote that this algorithm does not produce uniform random permutations. Assuming n=3, the algorithm can produce 3*3*3=27 outputs with 3 elements only 3! =6 different permutations, so that the probability of each permutation is equal to 1/6, then the number of permutations m must be such that m/27 is equal to 1/6, and obviously, no such integer is acceptable. In fact, the probability of each permutation is as follows. For example, the probability of {1,2,3} is 4/27, not 1/6.
| Rows of columns | Any rate |
|---|---|
| < 1, 2, 3 > | 4/27 |
| < 1, 3, 2 > | 5/27 |
| 3 > < 2, 1, | 5/27 |
| < 2, 3, 1 > | 5/27 |
| < 3, 1, 2 > | 4/27 |
| < 3, 2, 1 > | 4/27 |
2 Select a random number
Given a stream of integers of unknown length, how do we randomly select a number? (Randomness means that each number has the same probability of being picked.)
Solution 1: If the data stream is not very long, it can be stored in an array and then randomly selected from the array. Of course they’re talking about unknown length, so this solution has limitations if the length is too large to be stored in memory.
Solution 2: If the data stream is very long, we can do this:
- If the data flow ends after the first digit, the first digit is required.
- If the data stream ends after the second number, then the probability that we pick the second number is 1/2, and we replace the previous random number with the second number with a probability of 1/2 to get a new random number.
- .
- If the data stream ends after the NTH digit, the probability that we select the NTH digit is 1/n, that is, we replace the previously selected random number with the NTH digit with a probability of 1/n to obtain a new random number.
An easy way to do this is to use the random function f(n)=bigrand()%n, where Bigrand () returns a large random integer. When the data stream reaches the NTH number, if f(n)==0, it replaces the previously selected random number, ensuring that each number is selected with a probability of 1/n. For example, when n=1, f(1)=0, the first number is selected; when n=2, the probability of the second number being selected is 1/2; and so on, when the number length is N, the probability of the NTH number being selected is 1/n. The rand() function already returns a large random number on Linux/MacOS, just like bigrand()) :
void randomOne(int n)
{
int i, select = 0;
for (i = 1; i < n; i++) {
int rd = rand() % n;
if(rd == 0) { select = i; }}printf("%d\n", select);
}
Copy the code3 Select M numbers at random
The program input contains two integers m and n, where m
Solution 1: Consider a simple example. When m=2 and n=5, we need to select two ordered integers from 0 to 4 with medium probability and cannot repeat them. If we use the following criteria: Bigrand () % 5 < 2, then we have a 2/5 chance of picking 0. But we can’t pick 1 with the same probability, because if we pick 0, we should pick 1 with a 1/4 probability, and if we don’t pick 0, we should pick 1 with a 2/4 probability. The pseudocode selected is as follows:
select = m
remaining = n
for i = [0, n)
if (bigrand() % remaining < select)
print i
select--
remaining--
Copy the codeAs long as the condition m<=n is satisfied, the program outputs m ordered integers, no more, no less. It’s not going to do more than one, because every time I pick a number, SELECT –, I’m not going to do any more select when I get to zero. And it’s not going to be less, because every time remaining, when the select/remaining is equal to 1, it’s going to pick something. The probability of each subset being selected is equal. For example, there are C(5,2)=10 subsets, such as {0,1}, {0,2}… And so on, each subset has a 1 in 10 chance of being selected.
For a more general derivation, there are C(n,m) subsets of n choose M. Consider a particular sequence of m, such as 0… M-1, then the probability of selecting it is m/n * (m-1)/(n-1)*…. 1/(n-m+1)=1/C(n,m), and you can see that the probabilities are equal.
Grandpa Knuth proposed this algorithm very early, and his implementation is as follows:
void randomMKnuth(int n, int m)
{
int i;
for (i = 0; i < n; i++) {
if ((rand() % (n-i)) < m) {
printf("%d ", i); m--; }}}Copy the codeSolution 2: You can also use the idea of randomly arranging the array in front. First, arrange the first M numbers randomly, and then sort the m numbers and output it. The code is as follows:
void randomMArray(int n, int m)
{
int i, j;
int *x = (int *)malloc(sizeof(int) * n);
for(i = 0; i < n; i++) x[i] = i; // Random number groupfor(i = 0; i < m; i++) { j = randInt(i, n-1); swapInt(x, i, j); } // Sort the first m elementsfor (i = 0; i < m; i++) {
for(j = i+1; j>0 && x[j-1]>x[j]; j--) { swapInt(x, j, j-1); }}for (i = 0; i < m; i++) {
printf("%d ", x[i]);
}
printf("\n");
}
Copy the code4 RAND7 Generates rand10 problems
Given that a function rand7() can generate random numbers from 1-7 with equal probability for each number, give a function rand10() that can generate random numbers from 1-10 with equal probability for each number.
Solution 1: To generate random numbers 1-10, we either run RAND7 () twice or simply multiply a number to get the range value we want. As shown in formulas (1) and (2) below.
Independence idx = 7 * (rand7 () - 1) + rand7 () - (1) correct independence idx = 8 * rand7 () - 7 - (2) errorsCopy the codeFormula (1) above can generate random numbers from 1 to 49, why? Since the possible values of RAND7 () are 1-7, two RAND7 () may produce 49 combinations, which are exactly the 49 numbers 1-49, and the probability of each number is 1/49, so we can discard the ones greater than 40, and then take (IDX-1) % 10 + 1. Formula (2) is wrong because it produces numbers with unequal probability and does not produce 49 numbers.
1 2 3 4 5 6 7 8 9 10 1 4 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 10 * * 7 * * * * * * *Copy the codeThe solution is based on a method called rejected sampling. The main idea is to generate a random number within the target range, then directly return. If the generated random number is not in the target range, the value is discarded and re-sampled. Since the numbers in the target range are equally likely to be selected, such a uniform distribution is generated. The code is as follows:
int rand7ToRand10Sample() {
int row, col, idx;
do {
row = rand7();
col = rand7();
idx = col + (row-1)*7;
} while (idx > 40);
return 1 + (idx-1) % 10;
}
Copy the codeSince row ranges from 1-7 and COL ranges from 1-7, the IDX values range from 1-49. Values greater than 40 are discarded, leaving numbers in the range 1-40 that are returned by modulo. Let’s calculate the expected number of samples needed to get a number in the range 1-40:
E(# calls to rand7) = 2 * (40/49) +4 * (40/49) + 6 (9/49) * * 2 * (40/49) (9/49) +... Up = ∑ 2 k * * (40/49) (9/49) k - 1 k = 1 = (80/49) = 2.45/9/49 (1 -) 2Copy the codeSolution 2: The above method takes about 2.45 calls to rand7 to get a number in the range 1-10, which can be optimized again. For numbers greater than 40, we don’t have to discard them immediately. We can subtract 40 from the numbers 41-49 to get a random number from 1-9, while RAND7 generates a random number from 1-7 to generate a random number from 1-63. We can directly return 1-60 and discard 61-63, so that only 3 numbers need to be discarded. Compared with the previous 9, the efficiency is improved. For numbers 61-63, minus 60 to 1-3, RAND7 produces 1-7, which can be reused to produce numbers 1-21. For numbers 1-20 we return directly, and for numbers 21 we discard. At this point, the number of discarded is only 1, optimization is further. Of course, the number of calls to RAND7 has also increased. The code is as follows, and the optimized expectation is about 2.2123.
int rand7ToRand10UtilizeSample() {
int a, b, idx;
while (1) {
a = randInt(1, 7);
b = randInt(1, 7);
idx = b + (a-1)*7;
if (idx <= 40)
return 1 + (idx-1)%10;
a = idx-40;
b = randInt(1, 7);
// get uniform dist from 1 - 63
idx = b + (a-1)*7;
if (idx <= 60)
return 1 + (idx-1)%10;
a = idx-60;
b = randInt(1, 7);
// get uniform dist from 1-21
idx = b + (a-1)*7;
if (idx <= 20)
return1 + (idx-1)%10; }}Copy the code5 interesting probability questions
1) Weighing the ball problem
There are 12 balls, one of which is a bad ball. You are given a scale that requires you to weigh it the least number of times to determine which ball is broken and whether it is lighter or heavier.
Solution: We have summarized the binary search algorithm before, we know that binary search can speed up the search of ordered arrays. Similarly, in a number game, for example, if you were asked to guess a number between 1 and 64, you would be sure to guess it in six times using dichotomy. But the sphere-balancing problem is different. Let’s call the ball problem there are 12 balls, and the bad ball could be any one of them, so there’s 12 possibilities. And the bad ball could be heavy or light, so there are 12*2 = 24 possibilities. Each time, the balance can output three possibilities: balance, left weight and right weight. In other words, the possibility of a problem can be reduced to 1/3 by weighing once, so a total of 24 possibilities can be weighed in three times (3^3 = 27).
Why is the most intuitive way to call it6 -Not optimal? in6 -When you weigh it, the probability of balance is zero, and the optimal strategy would be to make the balance equally likely each time it is weighed, so that all the possibilities of the answer are equally divided.
How to implement it? Number the balls 1-12 and use the method of 4 and 4 weights.
- We will first
1 2 3 4和5 6 7 8Carry out the first weighing. - If you balance the first time, the bad ball is definitely there
9-12The number. Then you’re left with only9-12Four balls, the probability is zero9-10-11-12-9 + 10+ 11+ 12+These 8 possibilities. The following will9 10 11和1 2 3Call the second time: if equilibrium, then12No. 1 ball is a bad ball. Weigh no. 12 ball and No. 1 ball for the third time to confirm whether they are light or heavy. If it is not balanced, if it is heavy, it means that the bad ball is heavy. Continue to weigh the 9 and 10 balls. The heavy ball is the bad ball, and the balanced ball is 11. - If the first time is not balanced, the bad ball must be in
1-8 -The number. The remaining possibilities are 11+ 2+ 3+ 4+ 5- 6- 7- 8-orOne, two, three, four, five, six, seven, eightIf it is1 2 3 4If it’s heavy on this side, it can be1 2 6和3, 4, 5If it’s balanced, it must be7 8If it is lighter, weigh 7 and 1 again, then you can determine which 7 and 8 is the bad ball. If it’s not balanced, let’s say it’s1 2 6If this side is heavy, you can tell1 2The weight or5Lighter. Why is that? Because if it is3 + 4 + 6 -,1 2 3 4比5 6 7 8Heavy, but1 2 6Should be better than3, 4, 5Light. In other cases, you can find the bad ball at most 3 times.
The diagram below illustrates the principle more clearly.
2) Boys and girls
What is the ratio of boys to girls in countries where boys are preferred? In a country where boys are preferred, every family wants to have a boy, and if they have a girl, they have another one until they have a boy. What would be the ratio of boys to girls in such a country?
Solution: 1:1 again. For all first-born children, the male-to-female ratio is 1:1; For all second children born, the male-to-female ratio is 1:1; . For every NTH child born, the ratio is still 1:1. So the total ratio of men to women is 1:1.
3) Dating problems
Question: two people make an appointment at 5 to 6 o ‘clock in a place to meet, the first to wait for 20 minutes to leave, the probability of these two people can meet.
Solution: set respectively in the 5 X points and 5 Y to arrive, then they can meet the condition that | x-y | < = 20, while the scope for S = {(X, Y) : 0=< x <= 60, 0=< y <= 60}, if the axis is drawn, the situation is the area represented by the axis, probability is (60^ 2-40 ^2) / 60^2 = 5/9.
4) Hat problem
There are n customers. Each of them gives a hat to the waiter, who returns it to the customer in a random order. What is the expected number of customers who get their hat?
Solution: It is easier to solve the problem using indicated random variables. Let’s define a random variable X as equal to the number of customers who can get their hats, and we want to calculate E[X]. For I =1, 2… N, define Xi =I {customer I gets his hat}, then X=X1+X2+… Xn. Since the order of returning hats is random, the probability of each customer getting his hat is 1/n, i.e. Pr(Xi=1)=1/ N, thus E(Xi)=1/ N, so E(X)=E(X1 + X2 +… Xn)= E(X1)+E(X2)+… E(Xn)=n*1/n = 1, that is, about 1 customer can get his hat.
5) The birthday Paradox
How many people must there be in a room for two people to have the same birthday?
Solution: Define the indicator variable Xij= {I and J have the same birthday} for each pair (I, j) of people in room K, then Xij=1 if I and J have the same birthday, otherwise Xij=0. The probability of two people having the same birthday Pr(Xij=1)=1/n. If (X)=E(∑ki=1∑ KJ = I +1Xij) = C(k,2)*1/n = K (k-1)/2n, let k(K-1)/2n >=1, k>=28, that is, there must be at least 28 people, Can expect two people to have the same birthday.
6) Probability inverse problem
Question: If the probability of seeing a car pass in 30 minutes on the motorway is 0.95, what is the probability of seeing a car pass in 10 minutes? (Assuming constant probability)
Solution: If the probability of seeing a car pass in 10 minutes is x, then the probability of not seeing a car pass is 1-x, and the probability of not seeing a car pass in 30 minutes is (1-x)^3, which is 0.05. So we get the equation (1-x)^3 = 0.05, and solving the equation gives us x is about 0.63.
The resources
- Introduction to algorithms Chapter 6 Stochastic algorithms
- Programming Abas chapter 12
- Leetcode.com/articles/im…
- Mindhacks. Cn / 2008/06/13 /…
- Blog.csdn.net/wxwtj/artic…