0
$\begingroup$

I would like to write down an algorithm in mathematical notation. Now, I have some "ordered set" and remove some element $i$ and want to insert some element $k$ at the same position! So, $M \setminus i \cup k $ does not work because it "looks like" we inserted k at the end. It should just be at the position of i.

$\endgroup$
2
$\begingroup$

"Ordered set" that you speak about is a totally ordered set, i. e. a set with a antisymmetric, transitive binary relation $\le$ such that any pair of elements are comparable. Antisymmetric mean that from $a\le b$ and $b\le a$ it follows that $a=b$. Transitive mean that from $a\le b$ and $b\le c$ it follows that $a\le c$ (for example, relation "beats" in the rock-paper-scissors game is not transitive).

Let $(T,\le)$ be a totally ordered set (examples: integers with the "less or equal" relation, English words with the lexicographic order), $M$ be a subset of $T$.

After removing $i\in M$ from $M$ you get $M\setminus\{i\}$ with the total order $\le$ restricted to this set. After adding $k\in T$ into $M$ you get $M\cup \{k\}$ with the total order $\le$ restricted to this set.

So, once you define a totally ordered set $(T,\le)$ you can simply add and remove elements using $\cup$ and $\setminus$without any extra conditions.

$\endgroup$
  • $\begingroup$ Okay, but what if I want to insert some element not according to some global order but the position is just defined by where I insert it? So, let's say I have (10, 90, 40) and want to insert 50 after 90 = (10, 90, 50, 40)... I just dictate, 50 should be there, how can I write that? $\endgroup$ – IceFire Dec 1 '16 at 15:44
  • $\begingroup$ @IceFire, you can define a total order $\preceq$ such that $10\preceq 90\preceq 50\preceq 40$. $\endgroup$ – Canis Lupus Dec 1 '16 at 15:49
  • $\begingroup$ This means, I have to write the total order down each time I insert an element? So, if I have 100 elements and want to insert one at position 30, I need to write all of this down? $\endgroup$ – IceFire Dec 1 '16 at 15:53
  • $\begingroup$ You have to define only the final total. Or you can improve your question adding more specific details about your problem to find a better solution. (But anyway, the solution will be just another way to speak about the total order.) $\endgroup$ – Canis Lupus Dec 1 '16 at 15:58
  • $\begingroup$ Well, I want to insert and remove items due to some optimization algorithm which is nontrivial. I just want to move some element out and insert another one. There is no easy to define order as such but one that results from the algorithm $\endgroup$ – IceFire Dec 1 '16 at 16:00

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.