Algorithm to select a single, random combination of values?

by

Robert Floyd invented a sampling algorithm for just such situations. It’s generally superior to shuffling then grabbing the first x elements since it doesn’t require O(y) storage. As originally written it assumes values from 1..N, but it’s trivial to produce 0..N and/or use non-contiguous values by simply treating the values it produces as subscripts into a vector/array/whatever.

In pseuocode, the algorithm runs like this (stealing from Jon Bentley’s Programming Pearls column “A sample of Brilliance”).

initialize set S to empty
for J := N-M + 1 to N do
    T := RandInt(1, J)
    if T is not in S then
        insert T in S
    else
        insert J in S

That last bit (inserting J if T is already in S) is the tricky part. The bottom line is that it assures the correct mathematical probability of inserting J so that it produces unbiased results.

It’s O(x)1 and O(1) with regard to y, O(x) storage.

Note that, in accordance with the combinations tag in the question, the algorithm only guarantees equal probability of each element occuring in the result, not of their relative order in it.

1O(x2) in the worst case for the hash map involved which can be neglected since it’s a virtually nonexistent pathological case where all the values have the same hash

More Related Contents:

  1. Find all available combinations
  2. Different combinations of an array (C#)
  3. Algorithm to return all combinations of k elements from n
  4. Finding all possible combinations of numbers to reach a given sum
  5. All Possible Combinations of a list of Values
  6. How to generate all permutations of a string in PHP?
  7. Generate all combinations from multiple lists
  8. Generating combinations in c++
  9. Generate all binary strings of length n with k bits set
  10. PHP algorithm to generate all combinations of a specific size from a single set
  11. Find all combinations of a list of numbers with a given sum
  12. Creating all possible k combinations of n items in C++
  13. Javascript – Generating all combinations of elements in a single array (in pairs)
  14. How to generate all the permutations of a multiset?
  15. How to count possible combination for coin problem
  16. Algorithm to get all possible string combinations from array up to certain length
  17. Compute rank of a combination?
  18. PHP take all combinations
  19. Best way of calculating n choose k?
  20. How to generate the power-set of a given List?
  21. Howto create combinations of several vectors without hardcoding loops in C++?
  22. How to Generate Combinations of Elements of a List in .NET 4.0
  23. The intersection of all combinations of n sets
  24. How to efficiently calculate a row in pascal’s triangle?
  25. What’s time complexity of this algorithm for finding all combinations?
  26. counting combinations and permutations efficiently
  27. Algorithm to list all unique permutations of numbers contain duplicates
  28. O(3^n) exponential time complexity [closed]
  29. Difference between Big-Theta and Big O notation in simple language
  30. What is the algorithm for finding the center of a circle from three points?

Leave a Comment