17

I would like to know how to express mathematically $n$ largest values of a given set $A$.

For example: I have an unsorted set $A$ with $100$ values $\in \mathbb{N}$ and want to get a new set $B$ with the $5$ largest values.

Thank you in advance!

Start wearing purple
  • 53,234
  • 13
  • 164
  • 223
Chris
  • 181
  • 2
    Not every question with the word "set" is set theory. – Asaf Karagila Aug 09 '13 at 10:07
  • 1
    Can there be repeated values in $A$? Or will all of the numbers be distinct? Note that a set cannot have repeated values, in contrast with multisets (see Wikipedia). – Zev Chonoles Aug 09 '13 at 10:15
  • @AsafKaragila I feel leaving this naked and without tags is wrong (I feel that [notation] should be accompanied by another tag saying where the notation was encoutered, so this doesn't quite count - who follows [notation]?). However the only tag which I can think of which would fit would be [elementary-set-theory]. Surely this falls under elementary set theory, no? – user1729 Aug 09 '13 at 10:30
  • 2
    @user1729: I tend to agree, but this is not elementary set theory. This is, in fact, not anything that I can think of. Moreover, I can't think of any non-completely ad-hoc notation for this anyway. – Asaf Karagila Aug 09 '13 at 10:39
  • @AsafKaragila I agree entirely! But I wonder if tagging it that way is the best possible fit. – user1729 Aug 09 '13 at 10:40
  • Thank you for the suggestions and tagging correctly. @ZevChonoles Yes it would be a multiset. I declared that in the instructional text (of the paper) but not in my question. Sorry. Does that change something in the suggested answers? – Chris Aug 09 '13 at 10:52
  • @Chris Yes, it does change things! Simply because just taking the maximum won't work, because you might get three values as opposed to just one. However, just take $B$ to be $B:=B_i$, $|B_i|\geq 5$ but $|B_{i-1}|<5$ (note that this is not guaranteed to get for 5 on the nose, you need to remove some of the smallest elements for that. I'll edit my answer.). – user1729 Aug 09 '13 at 11:01
  • See also https://math.stackexchange.com/a/815096/361292 – beldaz Jul 31 '18 at 06:28

3 Answers3

26

$B={\rm argmax}_{A'\subset A, |A'|=n}\sum_{a\in A'} a $

smatsus
  • 261
6

I don't think you can do this in any easy way, unless you basically write a sentence to define the set. However, you could do it inductively:

Define $A=A_0$. Write $$B_1:=\{b\in A_0: b\geq a\:\forall\: a\in A_0\}$$ and define $A_1:=A_0\setminus B_1$. Then inductively, write $$B_{i+1}:=\{b\in A_i: b\geq a\:\forall\: a\in A_i\}$$ and define $A_{i+1}:=A_i\setminus B_{i+1}$. Then $B_5$ is the set you are after.

EDIT: In the comments you said that $A$ can be a multiset, and so can have more than one element of a given value. This means that, in the above, $B_5$ could be the entire set $A$. (For example, take $A=\{3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, \ldots\}$). So, what you want to do is set $\overline{B}:=B_i$ where $|B_i|\geq 5$ but $|B_{i-1}|<5$, set $C:=B_i\setminus B_{i+1}$ (these are the elements which we want to remove some of) and set $\overline{C}$ to be a subset of $C$ with $|\overline{B}|-5$ elements. Then take $B:=\overline{B}\setminus\overline{C}$.

There has to be a neater way though!

user1729
  • 31,015
2

It can be done using 5 iterations of removing the maximum element from set $A=A_0,A_1,\cdots,A4$ define $A_{k+1}=A_{k}-Max(A_k)$where a maximum exits, and let $B_k=A_{k}-A_{k+1} $ then the set $\cup_{k=0}^{4}B_k$ is the set of top 5 largest elements.

jimjim
  • 9,675