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:

  1. 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).
  2. We should first make an copy of the original array as we don’t want to modify it.
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: