Daten-Unsortierungs- / Homogenitätsalgorithmus

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.

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.

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.

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.