public static < T > Set < T > sampleHashingSetWithoutReplacement ( final Set < T > sourceSet , final int numSamples , final Random rng ) { checkArgument ( numSamples <= sourceSet . size ( ) ) ; // first we find the indices of the selected elements final List < Integer > selectedItems = distinctRandomIntsInRange ( rng , 0 , sourceSet . size ( ) , numSamples ) ; final Set < T > ret = Sets . newHashSet ( ) ; final Iterator < Integer > selectedItemsIterator = selectedItems . iterator ( ) ; if ( numSamples > 0 ) { // now we walk through sourceSet in order to find the items at // the indices we selected. It doens't matter that the iteration // order over the set isn't guaranteed because the indices are // random anyway int nextSelectedIdx = selectedItemsIterator . next ( ) ; int idx = 0 ; for ( final T item : sourceSet ) { if ( idx == nextSelectedIdx ) { ret . add ( item ) ; if ( selectedItemsIterator . hasNext ( ) ) { nextSelectedIdx = selectedItemsIterator . next ( ) ; } else { // we may (and probably will) run out of selected indices // before we run out of items in the set, unless the // last index is selected. break ; } } ++ idx ; } } return ret ; }
Given a hash - based set and a desired number of samples N will create a new set by drawing N items without replacement from the original set . This takes at least linear time in the size of the source set since there is no way to pick out arbitrary elements of a set except by iteration .