10
\$\begingroup\$

My goal is to pick 10 unique words randomly from a List containing 20 unique words.

I would remove the duplicate word from the List whenever a duplicate word is added and decrement the for loop counter by 1.

List<String> words = new ArrayList<String>();
/* code to add 20 words */

List<String> word10 = new ArrayList<String>();
for (i = 0; i < 10; i++) {
  int randomIndex = new Random().nextInt(words.size());
  if (word10.contains(words.get(randomIndex)) == true) {
    word10.remove(words.get(randomIndex));
    i--;
  }
  word10.add(words.get(randomIndex));
}
System.out.println("word10 List: " + word10);

Output

word10 List: [aah, abalone, aback, abandonee, abandonedly, abandon, abacus, aahed, aardvarks, abacuses]
word10 List: [a, aardvarks, aahing, abalones, abacuses, aahed, abacus, aah, abaft, abandoned]
word10 List: [abalones, ab, abaci, a, abacuses, abandonedly, aah, aahs, aardwolf, aardvark]

The code given is working properly. Is there a better approach?

\$\endgroup\$
2
  • 2
    \$\begingroup\$ Welcome to Code Review! Your first question looks good, I hope you get some good answers. \$\endgroup\$
    – Emily L.
    Nov 9, 2016 at 8:04
  • \$\begingroup\$ Why do you not just continue rather than remove and add if word10.contains \$\endgroup\$
    – paparazzo
    Nov 9, 2016 at 13:29

4 Answers 4

11
\$\begingroup\$

First off, don't make a new Random instance every iteration.

Secondly your approach is ineffective for larger numbers, and especially if the number of words to choose is closer to the number of words available. The odds that a word is not already among the chosen words can become so small it can take a long time for your code to complete. Imagine picking 1.000.000 words in random order from a list of 1.000.000, getting the last word is a 1 in a million chance to get right.

A simple but more efficient approach is to shuffle the words and then just take the head of the list :

List<String> words = new ArrayList<String>();
/* code to add 20 words */

Collections.shuffle(words);

System.out.println("word10 List: " + words.subList(0, 10));

Obviously you don't need to shuffle the entire list. You can write your own partial Fisher-Yates shuffle (basically swap your choices to the head of the list), that stops once enough of the list is shuffled. This is definitely a good choice if you're going to do this for large collections of words with only a small list to choose.

\$\endgroup\$
6
  • \$\begingroup\$ If you stop the shuffle then you eliminate cards from the shuffle \$\endgroup\$
    – paparazzo
    Nov 9, 2016 at 13:34
  • \$\begingroup\$ @Paparazzi yes, the ones you won't select for the result. You don't need to shuffle those. \$\endgroup\$
    – bowmore
    Nov 9, 2016 at 14:32
  • 1
    \$\begingroup\$ Do you have any specifics on the shuffle builtin? I would think that shuffling a list of 1 000 000 entries would take much longer than generating ten random numbers removing ten entries from the list, as the asker suggests. \$\endgroup\$
    – Devsman
    Nov 9, 2016 at 16:40
  • \$\begingroup\$ I disagree with this advice. Writing a partial Fisher-Yates is neither simpler nor significantly faster than OP's solution (unless the proportion of numbers selected becomes significant), but relies on mutable state. This is probably not expected by callers, and would therefore have to be documented. Moreover, it is an exceedingly bad idea if the word list is reused for other purposes, or used concurrently. \$\endgroup\$
    – meriton
    Nov 9, 2016 at 18:56
  • \$\begingroup\$ @Devsman Take a look at the Fischer Yates shuffle, which I already refered to. It treats the list as a shuffled part (the head) and an unshuffled (the tail) part. During the algorithm the shuffled part grows, as the unshuffled part shrinks. If we need only ten elements then we can prematurly end the shuffle as soon as the shuffled part has size 10. \$\endgroup\$
    – bowmore
    Nov 10, 2016 at 5:41
4
\$\begingroup\$

A better approach I would use is to use a Set instead of a List to do your gathering.

Set<String> candidates = new HashSet<>();
Random rand = new Random();

while(candidates.size() < 10) {
    String candidate = words.get(rand.nextInt(words.size());
    candidates.add(candidate);
}

List<String> word10 = new ArrayList<String>(candidates);

By doing this you make it very clear that you're adding to a list that requires uniqueness until you reach a threshold. Then you can keep your List requirement by creating a new list from the set.

If you don't care about it being a list but still want them in order, you could use a LinkedHashSet which maintains addition order.

\$\endgroup\$
1
\$\begingroup\$

Why add and remove from word10?
Creating a random in the loop in inefficient and not as random

List<String> words = new ArrayList<String>();
/* code to add 20 words */

List<String> word10 = new ArrayList<String>();
rand = new Random();
for (i = 0; i < 10; i++) {
  int randomIndex = rand.nextInt(words.size());
  string word = words.get(randomIndex);
  word10.add(word);
  words.remove(word);
}
System.out.println("word10 List: " + word10);
\$\endgroup\$
1
  • \$\begingroup\$ You can even do words10.add(words.remove(randomIndex)); \$\endgroup\$
    – bowmore
    Nov 9, 2016 at 15:38
1
\$\begingroup\$

Your choice of algorithm is nearly perfect as long as the number of elements selected is significantly smaller than the size of the wordlist (Otherwise, the number of duplicates starts to dominate the runtime, and you would be better off doing a partial sort on a copy of the array, as bowmore suggests).

However, like corsika, I'd use a Set for efficient duplicate testing.

You should create only a single instance of Random, and use that for all iterations of the loop, rather than creating a new instance of Random for every iteration. The reason is that Random's default constructor seeds its random number generator by the current system time, which on many platforms is updated infrequently enough that it will be the same for all iterations of the loop, causing you to draw the same random number many times.

Next, advancing and rewinding the loop variable in different statements makes it needlessly hard to understand the loop. I'd find it clearer to only modify the variable in one place. Same for removing and readding the same word to the result list.

As a matter of style, it is redundant to compare a boolean with true. That is, whenever you find yourself writing expr == true, you might as well simply write expr, but it has exactly the same meaning.

While we are on the subject of redundant code, type parameters provided to a constructor can usually be inferred by the compiler, so there is no need to specify them.

Finally, I'd probably move sampling to a new method, so I can give that method a meaningful name.

Therefore, I'd do it something like this:

Set<String> sampleWithoutReplacement(List<String> words, int count) {
    if (count > 0.8 * words.size()) {
        // fall back on bowmore's solution or throw an exception
    }

    Random random = new Random(); // might wish to move this to a field instead (but keep thread safety in mind)
    Set<String> results = new HashSet<>();
    while (results.size() < count) {
        results.add(words.get(random.nextInt()));
    }
    return results;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.