Daten-Unsortierungs- / Homogenitätsalgorithmus

8

Um ein Rad nicht neu zu erfinden, frage ich, ob jemand Ideen zu einem Datenhomogenitätsalgorithmus hat. Ein kurzes Beispiel:

Meine Daten haben vielleicht mehrere Elemente wie

  1. Nummer
  2. Farbe
  3. Obst
  4. Brief

Es gibt ungefähr 100 dieser Elemente in einem Array. Der Algorithmus muss die Elemente so sortieren , dass 2 Einträge mit derselben Nummer so weit wie möglich voneinander entfernt sind, und dasselbe gilt für Farbe, Obst usw. Es wäre auch schön, wenn ich die Elemente priorisieren könnte. Es fühlt sich so an, als würden Sie niemals 100% erreichen, also würden Sie ihm eine Reihe von Durchgängen geben, das Ergebnis überprüfen und dann weitere Durchgänge versuchen.

Es würde mich nicht wundern, wenn hier draußen etwas funktioniert, das ich nicht genug Google-Fu finden kann.

ExoByte
quelle
Haben Sie so etwas wie eine genetische Suche versucht ?
David Weiser
3
Du schreibst wie ein englischer Muttersprachler, also arbeite bitte ein bisschen an der Beschreibung. Bitte entfernen Sie das Wort "Gefällt mir", wo es nicht hingehört, und polieren Sie Ihre Sätze im Allgemeinen. Möchten Sie auch ein Beispiel geben? Ich habe Ihre Frage nicht vollständig verstanden.
Job
3
Beispiele sind wichtig. Ein Unit-Test-Fall ist für solche Dinge von entscheidender Bedeutung. Ein Textabschnitt ist kein Testfall.
S.Lott

Antworten:

2

Diese Art nervte mich für eine Weile, also musste ich kommen, um zu sehen, ob es gelöst wurde. Hier ist meine Idee. Von Grund auf neu, keine Anwendung eines mir bekannten Algorithmus. Dies wäre ein ziemlich teurer Brute-Force-Algorithmus, sollte aber ziemlich effektiv sein. Es wird davon ausgegangen, dass Sie mit dem von Ihnen beschriebenen relativ kleinen Datensatz (100 Zeilen mit 4 Spalten) arbeiten und auf einem modernen Computer mit ausreichend RAM arbeiten.

Übersicht : Wir verwenden einen rekursiven Algorithmus für eine sortierte Liste, um ähnliche Datensätze innerhalb ähnlicher Datensätze auf ihren maximalen Abstand zu verteilen. Nach jedem Anruf befinden sich alle Datensätze mit demselben übergeordneten Element in maximaler Entfernung. Der Top-Aufruf enthält alle Datensätze. So wird es von innen nach außen unsortiert.

Datenstrukturen :

  • newIndexesist ein array<integer>. Der Index des Arrays ist der vorhandene Index der Zeile. Der Wert ist der neue Index und beginnt mit -1
  • dataist ein array<array<string>>. Der Schlüssel ist der Index, das innere Array ist eine Zeichenfolgendarstellung der Werte in einer Zeile. Muss keine Zeichenfolge sein, wenn Sie Ihre Daten gruppieren möchten. Das erste Array-Element ist das mit dem größten Gewicht.

Nach dataGewichtsreihenfolge sortieren . Sortieren Sie es zuerst nach der Spalte mit dem größten Gewicht, innerhalb dieser nach der Spalte mit dem zweitgrößten Gewicht usw. Das Ergebnis ist die Umkehrung dessen, was Sie wollen. Index nacheinander.

Hier ist der Algorithmus (im Psudo-Code).

        // siblingCount: On first call is the number of rows in the table,
    //    on recursive calls it is the number of elements with the same parent
    // index: the index of current row in `data` - starts 0
    // depth: The element index - starts 0
    void unsort(int siblingCount, int index, int depth)
    {
        int count = 1;
        string hash = concatColumns(index, depth + 1);
        while ((index + count < data.count) && (hash == concatColumns(index + count, depth + 1)))
        {
            count++;
        }

        if (depth < columnCount)
            unsort(count, index, depth);
        else if (index < data.count)
            unsort(count, index + count, 0);

        int spacing = siblingCount / count;

        for (int i = 0; i < count; i++)
        {
            var offset = 0;
            while ((newIndexes[index + i + offset] > -1) & (index + i + offset + 1 < newIndexes.count))
                offset++;

            if (newIndexes[index + i + offset] > -1) throw new Exception("Shouldn't happen.");

            newIndexes[index + i + offset] = index + spacing * i;
        }
    }

    string concatColumns(int index, int count) // returns count columns concatinated
    {
        // 1,1 = "1"
        // 1,2 = "1, blue"
        // 1,3 = "1, blue, apple"
        return "1, blue, apple";
    } 

Wenden Sie dann die newIndexes auf die zu unsortierenden Daten an.

Überlegungen zum Ansatz: Ich habe dies nicht getestet, aber das Speichern der neuen Indizes und das Lösen von Konflikten kann problematisch sein, da die ersten Indizes basierend auf niedrigstwertigen Spalten zugewiesen werden. Wenn also viele Konflikte vorliegen, können sich die höherwertigen Spalten gruppieren. Versuchen Sie möglicherweise, den Offset zuerst als positiv und dann als negativ anzuwenden. Oder fügen Sie dies möglicherweise in eine verknüpfte Liste anstelle eines Arrays ein.

Jim McKeeth
quelle
Ah! Ich sehe sehr, was Sie hier vorhaben. Sortieren und dann nach der Größe der Gleichheitskette trennen. Wenn dies nicht sofort funktioniert, sollte es ziemlich nah sein. Vielen Dank für Ihre Hilfe und die Bereinigung der Frage! Hoffentlich kann ich das ausprobieren, wenn ich diese Art von Daten das nächste Mal im September verarbeiten muss
ExoByte
Lassen Sie mich wissen, wie es funktioniert.
Jim McKeeth
4

Das erinnert mich an einen Netzwerkalgorithmus, den ich gesehen habe, das Schlüsselwort 'tkwikibrowser' 'TouchGraphWikiBrowser', bei dem die Elemente mit einer Art Gummiband kombiniert werden, aber wie Magnete desselben Pols sind.

Ich weiß nicht, wie die Mechanik in Ihrem Fall aussehen würde, aber vielleicht ist 'Fall' das richtige Schlüsselwort: Die Elemente werden in einen Fall eingefügt und vom Rand des Falls weggeschoben und drücken sich gegenseitig weg Dies gilt umso mehr, wenn sie mehrere Attribute gemeinsam haben.

Sie beginnen in zufälligen Positionen und bewegen sich in Abhängigkeit von der Entfernung zur Wand und der Entfernung zu ähnlichen Elementen und suchen eine stabile Position.

Die Formel, um sich gegenseitig wegzuschieben, kann linear oder quadratisch zur Entfernung sein, und Sie können live nach einer guten Formel suchen, indem Sie die Werte manipulieren.

aktualisieren:

Für die anziehende Kraft könnte man einfach die Umkehrung der ablenkenden Kraft nehmen. Wenn also 2 Elemente kein einziges Attribut gemeinsam haben, ist dies die maximale Anziehungskraft.

Benutzer unbekannt
quelle
OK, ich werde beißen. Ich habe eine Google-Suche auf tkwikibrowser durchgeführt und nichts bekommen. Können Sie auf weitere Informationen verlinken?
Jim McKeeth
Sie haben Recht, es tut mir leid, der Name war nicht TKWiki ..., sondern TGWiki ... für TouchGraph, wie hier , aber ich habe nur diesen Screenshot gefunden, keine funktionierende Demo, in der sich die Knoten wie auf einem Gummiband bewegen .
Benutzer unbekannt
3

Verwenden Sie eine zufällige Zufallswiedergabe oder sortieren Sie die verketteten Daten nach einem Hash: Ein guter Hash liefert sehr unterschiedliche Ausgaben für ähnliche Eingaben. Daher sollten Einträge, die in einer beliebigen Dimension ähnlich sind, getrennt werden.

Jon Purdy
quelle
1
Dies scheint die einfachste Lösung zu sein, aber jetzt bin ich wirklich gespannt, wie sich dies mit Daten aus der realen Welt verhalten würde.
TheLQ
Das Problem dabei ist, dass ein ähnlicher Hash unähnlich ist. Ein Hash identischer Zeilen würde denselben Hash erzeugen und dann sortieren, um benachbart zu sein.
Jim McKeeth
Und es werden exakte Duplikate in den Daten sein. Dies könnte jedoch ein interessanter Ausgangspunkt sein.
ExoByte
@ Jim McKeeth: Richtig, du bist. Natürlich können Sie auch einen Index verketten, um ansonsten identische Zeilen durch eine kleine Anzahl von Bits zu unterscheiden. Sie können sich auch Kurven der Z-Ordnung ansehen (trivial durch Bitverschachtelung erhalten), die lineare Daten räumlich so verteilen, dass Daten in der Nähe so bleiben. Sie suchen nach einer Permutation, die das Gegenteil davon liefert.
Jon Purdy