3. Zahlenfelder durchmischen

Zahlenfelder durchmischen

  • R

    Hi,

    es gibt ja zahlreiche Dokumentationen zu Algorithmen, die Zahlen nach einem bestimmten Schema (Variable, Größe usw.) durchmischen - BubbleSort, QuickSort usw.

    Ich bin auf der Suche nach einem Algorithmus, der genau das Gegenteil macht, also beispielsweise ein int-array nach einem bestimmten Schema durchmischt... kennt eine von Euch entsprechende Möglichkeiten (nicht zu kompliziert)?

    Wichtig ist mir dabei, dass kein Zufall mit im Spiel ist 🙂

    Danke für eure Tipps!
    Johannes

    0
  • _

    Du willst durchmischen, aber nichr sortieren, doch es soll kein Zufall im Spiel sein? Ist das kein Widerspruch?

    0
  • Z

    du kannst std::sort deine eigene Sortiermethode / -klasse mitgeben.

    0
  • N

    _matze schrieb:

    Du willst durchmischen, aber nichr sortieren, doch es soll kein Zufall im Spiel sein? Ist das kein Widerspruch?

    Er meint wahrscheinlich, dass Permutationen nach genau definierten Regeln erfolgen sollen. Vielleicht sind die STL-Algorithmen next_permutation() und ähnliche etwas für dich...

    Abgesehen davon ist bei der Programmierung sowieso fast nie echter Zufall im Spiel 😉

    zwutz schrieb:

    du kannst std::sort deine eigene Sortiermethode / -klasse mitgeben.

    Er will aber das Gegenteil machen 🙂

    0
  • N

    Wenn etwas nach bestimmten Regeln in eine neue Reihenfolge gebracht wird und beim selben Input immer derselbe Output generiert wird, dann nenn ich das Sortieren...
    Edit: Klar ist Mischen dann auch eine Art Sortieren... bei srand(konstanterwert) und anschließendem "Mischen" ist garantiert kein Zufall im Spiel.

    0
  • ?

    Nanyuki schrieb:

    Wenn etwas nach bestimmten Regeln in eine neue Reihenfolge gebracht wird und beim selben Input immer derselbe Output generiert wird, dann nenn ich das Sortieren...
    Edit: Klar ist Mischen dann auch eine Art Sortieren... bei srand(konstanterwert) und anschließendem "Mischen" ist garantiert kein Zufall im Spiel.

    sehe ich auch so

    0
  • R

    Ja richtig. Im Endeffekt suche ich einen Sortier-Algorithmus. Allerdings nicht nach dem Kriterium "aufsteigend/absteigend" sondern nach einem anderen... das mit den Permutationen sieht interessant aus. Allerdings weiß ich nicht, ob man damit auch arrays mit 2000+ Einträgen bearbeiten kann... mal testen 🙂

    0
  • N

    Nanyuki schrieb:

    Wenn etwas nach bestimmten Regeln in eine neue Reihenfolge gebracht wird und beim selben Input immer derselbe Output generiert wird, dann nenn ich das Sortieren...

    Ja, nur ist das eher nicht das, was meistens unter Sortieren verstanden wird (bei dem das einzige Kriterium auf paarweisen Vergleichen beruht, und dass dieses Kriterium bei der sortierten Sequenz jeweils auf zwei aufeinanderfolgende Elemente zutrifft). Und was selber Input = selber Output betrifft: Das hast du fast immer im Programmieren, wenn du nichts Undefiniertes tust.

    Nanyuki schrieb:

    Edit: Klar ist Mischen dann auch eine Art Sortieren... bei srand(konstanterwert) und anschließendem "Mischen" ist garantiert kein Zufall im Spiel.

    Wie gesagt ist bei keinem Aufruf von rand() oder std::random_shuffle() auch nur ein bisschen Zufall im Spiel, egal ob srand() vorher einen konstanten Wert genommen hat oder nicht.

    0
  • N

    Roque schrieb:

    das mit den Permutationen sieht interessant aus.

    Die Sequenz erscheint jedoch dann auch nicht wirklich zufällig, sondern es ist dann eben so, dass die erste Permutation eine aufsteigend und die letzte eine absteigend sortierte Sequenz ist. Zwischendrin werden dann systematisch Elemente vertauscht.

    Falls du eher etwas suchst, wo die ganze Sequenz pseudozufällig neu geordnet wird, ist vielleicht das eine Hilfe, das ist allerdings schon ein wenig komplexer...

    Wenn es dir reicht, einfach neu zu ordnen und wenn du nicht nacheinander alle möglichen Permutationen durchgehen musst, kannst du auch std::random_shuffle() verwenden.

    Roque schrieb:

    Allerdings weiß ich nicht, ob man damit auch arrays mit 2000+ Einträgen bearbeiten kann... mal testen 🙂

    Mit der STL sollte das kein Problem sein. Einen eigenen Algorithmus musst du eben effizient implementieren (wobei auch da 2000 noch gut gehen sollte) 😉

    0
  • Z

    Nexus schrieb:

    zwutz schrieb:

    du kannst std::sort deine eigene Sortiermethode / -klasse mitgeben.

    Er will aber das Gegenteil machen 🙂

    Was diese Sortiermethode macht, bleibt ja ihm ueberlassen. Hauptsache, sie gibt true zurueck, wenn der erste der erste der beiden Parameter derjenige ist, der vorne stehen muss (in der Regel also kleiner ist)

    0
  • N

    zwutz schrieb:

    Was diese Sortiermethode macht, bleibt ja ihm ueberlassen. Hauptsache, sie gibt true zurueck, wenn der erste der erste der beiden Parameter derjenige ist, der vorne stehen muss (in der Regel also kleiner ist)

    Ja, aber damit kann man trotzdem nur eine Sequenz bilden, bei der für jeweils zwei benachbarte Elemente das Vergleichskriterium zutrifft. Permutationen kommen also nicht in Frage...

    0
  • Z

    bis jetzt hat er noch nicht gesagt, wie er "sortieren" will...

    0
  • N

    Naja, die folgenden Aussagen haben mich das vermuten lassen:

    Roque schrieb:

    Ich bin auf der Suche nach einem Algorithmus, der genau das Gegenteil macht, also beispielsweise ein int-array nach einem bestimmten Schema durchmischt...

    Roque schrieb:

    Im Endeffekt suche ich einen Sortier-Algorithmus. Allerdings nicht nach dem Kriterium "aufsteigend/absteigend" sondern nach einem anderen... das mit den Permutationen sieht interessant aus.

    Und das ist schliesslich nicht mit einem Funktor als Übergabe an die Sortierfunktion zu lösen 😉

    0
  • Administrator

    Nexus schrieb:

    Naja, die folgenden Aussagen haben mich das vermuten lassen:

    Roque schrieb:

    Ich bin auf der Suche nach einem Algorithmus, der genau das Gegenteil macht, also beispielsweise ein int-array nach einem bestimmten Schema durchmischt...

    Roque schrieb:

    Im Endeffekt suche ich einen Sortier-Algorithmus. Allerdings nicht nach dem Kriterium "aufsteigend/absteigend" sondern nach einem anderen... das mit den Permutationen sieht interessant aus.

    Und das ist schliesslich nicht mit einem Funktor als Übergabe an die Sortierfunktion zu lösen 😉

    Wieso? Sicher geht das!

    class RandomSort
{
public:
  template<typename FirstT, typename LastT>
  bool operator ()(FirstT const&, LastT const&)
  { return static_cast<bool>(rand() & 1); }
};

// Irgendwo:
std::sort(container.begin(), container.end(), RandomSort());

    Grüssli 🙂

    0
  • Z

    lass mich doch auch mal was hilfreiches sagen 😞

    vll will er ja zuerst alle ungeraden und dann alle geraden in seiner Liste haben, vll will er die Zahlen nach der Anzahl der gesetzten Bits sortieren oder nach ihrem Abstand zur naechsten Primzahl oder nach der Anzahl der Primfaktoren... alles Faelle, wo ausnahmsweise ich mal recht haette 😉

    0
  • N

    Naja, es ist sicher das Beste, wenn wir einfach darauf warten, dass er sich genauer ausdrückt 🙂

    0
  • Administrator

    zwutz schrieb:

    vll will er ja zuerst alle ungeraden und dann alle geraden in seiner Liste haben, vll will er die Zahlen nach der Anzahl der gesetzten Bits sortieren oder nach ihrem Abstand zur naechsten Primzahl oder nach der Anzahl der Primfaktoren... alles Faelle, wo ausnahmsweise ich mal recht haette 😉

    Das wären aber alles Fälle, welche auf- oder absteigend sind. Und das will er ja nicht 🙂
    Deshalb bin ich auch davon ausgegangen, dass er etwas zufälliges will, was er aber auch nicht will, oder doch? 😕
    Ich habe KEINE AHNUNG was er will 🙂

    Grüssli

    0
  • R

    Heieiei... an dieser Stelle erst Mal vielen Dank für das klasse Feedback 🙂

    In erster Linie suche ich ein mathematisches Verfahren, mit dem man geordnete Zahlenfelder systematisch durchmischen kann - beispielsweise in Abhängigkeit einer int-Variable. Hintergrund ist folgender: Ein Modul meines Verschlüsselungs-Algorithmus liest den eingegebenen Text buchstabenweise in eine Matrix (d.h. jede Zelle ein Buchstabe). Neben der Matrix existiert ein Array, welches genau so viele Einträge besitzt wie Zellen der Matrix.

    Dem geordneten Array wird also jedem Eintrag eine Position in der Matrix zugeordnet. Wenn ich jetzt systematisch das Array durchmische ändert sich die Position eines jeden Buchstabens in der Matrix - das soll eben ein Teil der Verschlüsselung werden. Fein wäre es eben, wenn diese "Verteilung" möglichst homogen wäre - also quasi "zufällig" verteilt wird.

    Kann sein dass es auch eine viel elegantere Lösung dazu gibt... über Tipps wäre ich Euch sehr dankbar 🙂

    Grüße
    Johannes

    0
  • Administrator

    Also doch ein Randomschuffle, nur möchtest du einen etwas besseren Zufallgenerator, bzw. mehr Kontrolle darüber? Dann schau mal in die Boost Libraries, da findet man eine Lib mit dem wunderschönen Namen Random.

    Grüssli

    0
  • Z

    ich war doch wieder falsch 😞

    0
  • N

    Dravere schrieb:

    Also doch ein Randomschuffle, nur möchtest du einen etwas besseren Zufallgenerator, bzw. mehr Kontrolle darüber? Dann schau mal in die Boost Libraries, da findet man eine Lib mit dem wunderschönen Namen Random.

    Ich weiss nicht, ob es mit einem Zufallsgenerator möglich ist, alle möglichen Permutationen nacheinander durchzugehen und jede einzelne Permutation eindeutig per Integer ansprechen zu können...

    Wahrscheinlich kommt man da nicht drum herum, tiefer in die Materie einzusteigen und sich mathematisch damit auseinanderzusetzen. Würde mich übrigens auch noch interessieren, wie das möglich wäre 😉

    0
Anmelden zum Antworten