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.

  • 0
    I don't understand the question. What's wrong with just choosing the first $K$ elements? What does "generic" mean?2012-04-16
  • 0
    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...)2012-04-16
  • 0
    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.)2012-04-16
  • 0
    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.2012-05-03

1 Answers 1