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$
  • $\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.