## Randomly generate m integers from an array of size n

Write a method to randomly generate a set of m integers from an array of size n Each element must have equal probability of being chosen.

My initial thoughts:
Maintain the following loop: randomly select an element from the right part and swap it with the i-th element from 0 to m at the left part. Output the first m element in the array.

My initial codes:

```	public static int[] chooseNFromM(int[] array, int m) {
if (m > array.length)
return null;
int[] results = new int[m];
for (int i = 0; i < m; ++i) {
int index, temp;
do {
index = new Random().nextInt(array.length);
} while (index < i);
temp = array[index];
array[index] = array[i];
array[i] = temp;
}
for (int i = 0; i < m; ++i) {
results[i] = array[i];
}
return results;
}

Solution:
Please refer to the book: Cracking the Coding Interview.
Comments:

We don’t need to keep generating random numbers. We just need to label which ones are ‘dead’ (in this case, 0 to i) and generate random index in the valid range (i+1 to n).
We should first make an copy of the original array as we don’t want to modify it.

__ATA.cmd.push(function() {
__ATA.initVideoSlot('atatags-370373-5c910cefc1b6a', {
sectionId: '370373',
format: 'inread'
});
});

Advertisements

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-26942-5c910cefc1bad',  {
collapseEmpty: 'before',
sectionId: '26942',
width: 300,
height: 250
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-114160-5c910cefc1bb0',  {
collapseEmpty: 'before',
sectionId: '114160',
width: 300,
height: 250
});
});

Like this:Like Loading...

Related
```