Take the 2-minute tour ×

I want to repeatably (i.e. in deterministic way) select 10% (or K%, $K \in (0,100]$) of elements in a set S.

The only way to do so I can imagine, is having an $order(S)$, which is a sequence. Then (assuming |S| = 100) simply select every 100/K-th element. Or first K elements, etc.

I wonder how generic can be this deterministic choose operation? Can something different than order be used? My aim is to denote all possible deterministic methods, to then prove a property that I think holds, if only the selection is deterministic.

share|improve this question
I don't understand the question. What's wrong with just choosing the first $K$ elements? What does "generic" mean? –  JeffE Apr 16 '12 at 7:08
And for that matter, what does 'it is not repetitive' mean? (There are ways of randomly picking exactly $m$ things from a set of $n$, so ways of randomly picking $K/10$ things from $K$ if that's what you're looking for...) –  Steven Stadnicki Apr 16 '12 at 7:14
What property? Once a magic black box emits a subset of elements, how can any property of that subset depend on whether the black box is deterministic? (Give me two different black boxes whose outputs always have the property you want. I'll build a bigger black box that chooses one of your black boxes by flipping a coin. The output of my bigger black box always has the property you want.) –  JeffE Apr 16 '12 at 13:39
If you're talking about a fixed set $S$, this doesn't make sense: any subset can be selected by a deterministic algorithm. However, perhaps you are really talking about an infinite family of $S$'s, using the same algorithm for all (with an input telling it what $S$ is) and then things become interesting. –  Robert Israel May 3 '12 at 7:08

1 Answer 1

I assume you mean "repeatably", not "repetitively". How about defining some kind of hash function on the members of the set; so that each member of the set maps to an integer, and the integer values are reasonably spread.

Then each element is selected if the last two digits of its hash value make a 2-digit number less than K.

share|improve this answer

Your Answer


