Definieren Sie das Sortierproblem, indem Sie mathematisch angeben was gegeben und was gesucht ist.

Question

Ich hätte folgene Idee:

Gegeben: $$ A=\begin{pmatrix} { a }_{ 1 }\\...\\{ a }_{ n } \end{pmatrix} für \quad n∈ℕ $$

Gesucht:

Ein Vektor  \( B=\begin{pmatrix} { b }_{ 1 }\\...\\{b}_{ n } \end{pmatrix} \)für dass gilt:
$$ \left\{ b|\quad∀a\exists !b : \quad b=a \quad ∧ \quad { b }_{ 1 }≤{ b }_{ 2 }≤...≤{ b }_{ n }\right\}.$$

Könnte man es so definieren oder liege ich vollkommen falsch? Hätte jemand einen besseren Vorschlag?

Answer 1

∀a∃!b b=a ergibt keinen Sinn. Woher kommen die a und die b? Der Rest sieht gut aus.

Ich glaube du meinst ∀i∈{1,...,n}∃j∈{1,...,n} a_i=b_j.

Problem dabei ist allerdings, dass 3 Fünfer und 2 Siebener in A zu 3 Siebener und 2 Fünfer in B "umsortiert" werden können. Das kann man dadurch reparieren, dass man stattdessen die Existenz einer bijektiven Abbildung p auf {1,...,n} verlangt, die a_i=b_p(i) für alle i aus {1,...,n} erfüllt.

Comments

Aus den Elementen der Vektoren. Ich wollte definieren, dass die Werte identisch sind.

---

Ich weiß. Das kann man deiner Formalisierung aber nicht entnehmen.

---

Ach so, also würde es korrekt so heißen?

Gesucht:

Ein Vektor  \( B=\begin{pmatrix} { b }_{ 1 }\\...\\{b}_{ n } \end{pmatrix} \)für dass gilt:
$$ \left\{ { ∀ }_{ i }∈\left\{ 1,...,n \right\} { ∃ }_{ j }∈{ \left\{ 1,...,n \right\}}:{ a }_{ i }={ b }_{ j } \right\} $$

---

Da ist noch ein Probem aufgetaucht, siehe aktualisierte Antwort. Und die Bedingung b₁≤ ... b_n.brauchst du auf jeden Fall noch.

---

Ok, vielen Dank. Wie wäre es so?

---

Statt {∀i∈{1,...,n}∃j∈{1,...,n} a_i=b_j} würde ich einfach dann {∀i∈{1,...,n}: a_i=b_p(i), b₁≤ ...≤b_n} schreiben. Oder wäre es etwas zu einfach?

---

Wenn du zusätzlich noch erwähnst, dass p:{1,...,n}→{1,...,n} bijektiv ist, dann reicht das.

---

Vielen vielen Dank nochmal.

Answer 2

Hey Sam94, ich habe gerade nach einer Aufgabenlösung gesucht und bin auf dein Profil gestoßen. Kann es sein, dass du Student bist und Algorithmen und Datenstrukturen gehört hast weil du Info studierst. Das wäre echt cool... Ich auch wäre cool wenn du dich mal melden kannst.

Comments

Oh, leider habe ich erst jetzt die Nachricht gesehen. Anscheinend bist du nicht mehr online gewesen leider seitdem. Aber falls du mal hier hinkommst wieder, ich bin von hier erreichbar.