4
$\begingroup$

I have a set $S$ with 100 elements, and a very simple function defined over my set $f : S → [0, 1]$. This function simply tells me how "good" an element is (this function is strictly monotonous).

Now I want to define a subset $G \subset S$, which contains the top 10 best elements in $S$, i.e. those for which $f(x)$ gives the highest 10 values.

How do I write $G$ in short set-builder notation?

I had an idea about repeatedly using $\underset{x \in S}{\operatorname{argmin}} ~f(x)$, where $S$ kept shrinking, namely $S_i = S_{i-1} - \{\underset{x \in S}{\operatorname{argmin}}~f(x)\}$, and after 90 iterations, $S_{90}$ would be my "top 10" set. But I have no idea how to write these iterations in set-builder notation.

$\endgroup$
8
  • $\begingroup$ Using argmax, you only need 10 steps rather than 90... :) $\endgroup$
    – Dirk
    Apr 18 '17 at 9:17
  • $\begingroup$ Your function $f$ is not necessarily injective? So exactly hos is the subset $G$ defined in case of ties, e.g., if $f$ happens to be a constant function? $\endgroup$
    – bof
    Apr 18 '17 at 9:19
  • $\begingroup$ I thought about argmax, but it seemed even more hopeless to write set-builder notation for it. I'd need to write that "$G$ are those elements given by argmax, and then remove it, then apply argmax again, and at the end see what the repeated argmax found in the past". No idea how. $\endgroup$
    – CamilB
    Apr 18 '17 at 9:19
  • 2
    $\begingroup$ If $f$ is injective you could use $$G=\{x\in S:|\{y\in S:f(x)\lt f(y)\}|\lt10\}.$$ Of course, if $f$ is not injective, that $G$ could have more than $10$ elements. $\endgroup$
    – bof
    Apr 18 '17 at 9:22
  • 1
    $\begingroup$ Note that injectivity of $f$ follows from strict monotonicity. $\endgroup$
    – Dirk
    Apr 18 '17 at 9:30
7
$\begingroup$

Given a set $S$ with $|S|\ge10$ and a function $f:S\to\mathbb R,$ the set $$G=\{x\in S:|\{y\in S:f(x)\lt f(y)\}|\lt10\}$$ consists of the "best" $10$ elements of $S,$ including all elements tied for one of the top ten places. (Elements with greater $f$-values are considered "better".)

$\endgroup$

This site is temporarily in read only mode and not accepting new answers.

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