0
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ I don't understand the question. What's wrong with just choosing the first $K$ elements? What does "generic" mean? $\endgroup$
    – JeffE
    Apr 16, 2012 at 7:08
  • $\begingroup$ 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...) $\endgroup$
    – Steven Stadnicki
    Apr 16, 2012 at 7:14
  • $\begingroup$ 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.) $\endgroup$
    – JeffE
    Apr 16, 2012 at 13:39
  • $\begingroup$ 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. $\endgroup$
    – Robert Israel
    May 3, 2012 at 7:08

1 Answer 1

Reset to default
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .