Assume I have a set $S=\{1,\ldots,n\}$ that is not necessarily indexed. Since sets are inherently unordered, I would like to make a sequence $a=(a_1,\ldots,a_n)$ of the elements in $S$ such that $a_1<\cdots<a_n$.

I guess I need to map the values somehow, but how to do it? Note that I write sequence here rather than tuple since all the elements in $S$ are integers, in case it makes any difference. Maybe there are other, better ways than the one proposed above.

  • 2
    $\begingroup$ This doesn't really make sense to me. Can you give a specific example of a set $S$ that you're interested in, e.g., $S=\{17,3,99\}$? Is it accurate to say that your question is "Given a finite list of integers, not necessarily in order, what is an algorithm for putting them in order?" $\endgroup$ – Zev Chonoles Sep 7 '16 at 20:54
  • $\begingroup$ Not enough information. What is $<$, as you don't really say what kind of elements $S$ has? $\endgroup$ – avs Sep 7 '16 at 20:59
  • $\begingroup$ The elements in the set are integers. $\endgroup$ – index Sep 7 '16 at 21:20
  • $\begingroup$ Are you asking about sorting algorithms? $\endgroup$ – ajotatxe Sep 7 '16 at 21:21
  • $\begingroup$ Are you looking for something like"We index the elements of $S$ in ascending order." or is this question about something else? $\endgroup$ – Arthur Sep 7 '16 at 21:24

After looking at the comments, it seems to me that you're asking about sorting algorithms (Wikipedia), which are certainly a part of mathematics, in the area of theoretical computer science (there's a separate Stack Exchange site for it though; here's the list of questions on sorting).

Sorting algorithms are usually discussed in terms of asymptotic analysis (as the size of the list of things to be sorted grows, how does the amount of time it takes to sort grow), their efficiency in some aspect (e.g. if comparing two elements of the set will take a long time, you may want to choose an algorithm that makes few comparisons), or their suitability given assumptions about the data (e.g., whether the data will already be "mostly" sorted).

For a simple example of a sorting algorithm, look at selection sort (Wikipedia): given the set $S$,

  • Let $a_1=\min(S)$

  • Let $a_2 = \min(S\setminus\{a_1\})$

  • Let $a_3 = \min(S\setminus\{a_1,a_2\})$

  • ...

  • $\begingroup$ This is a really nice way to formulate it, thanks. One question though: Is there a way to represent it as maybe some kind of sorting function or mapping $f:S→\{(a_1,…,a_n):a_1<⋯<a_n\}$? $\endgroup$ – index Sep 8 '16 at 9:54

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.