Algoritmo "unsort" / omogeneità dati

Questo tipo di bug mi ha bloccato per un po 'quindi ho dovuto venire a vedere se è stato risolto. Ecco la mia idea Da zero, non un'applicazione di alcun algoritmo di cui sono a conoscenza. Questo sarebbe un algoritmo di forza bruta piuttosto costoso, ma dovrebbe essere abbastanza efficace. Si presume che tu abbia a che fare con il set di dati realmente piccolo che hai descritto (100 righe di 4 colonne) e stia lavorando su un computer moderno con RAM sufficiente.

Panoramica : utilizziamo un algoritmo ricorsivo su una lista ordinata per disperdere record simili alla loro distanza massima all'interno di record simili. Dopo ogni chiamata tutti i record con lo stesso genitore sono alla loro massima distanza. La prima chiamata include tutti i record. Così si risolve dall'interno.

Strutture dati :

• newIndexes è un array<integer> . L'indice dell'array è l'indice esistente della riga. Il valore sarà il nuovo indice, inizia con -1
• data è un array<array<string>> . La chiave è l'indice, l'array interno è una rappresentazione di stringa dei valori in una riga. Non ha bisogno di essere una stringa se hai qualche modo di raggruppare i tuoi dati. Il primo elemento dell'array è quello con il peso maggiore.

Ordina data in base all'ordine di peso. Ordinalo prima per la colonna con il peso più grande, all'interno di quello per colonna con il secondo più grande peso, ecc. Il risultato è l'inverso di ciò che desideri. Indice in sequenza.

Ecco l'algoritmo (nel codice psudo).

        // 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";
    } 

Quindi applica i nuoviIndex ai dati da non ordinati.

Pensieri sull'approccio: non l'ho verificato, ma la memorizzazione dei nuovi Indici e la risoluzione dei conflitti possono essere problematici dal momento che i primi indici vengono assegnati in base a colonne meno significative, quindi se ci sono molti conflitti, le colonne più significative può cluster. Potrebbe provare a applicare l'offset come prima positivo, poi negativo. O forse fare una sorta di inserimento in una lista collegata invece di una matrice.

Questo mi ricorda un algoritmo di rete che ho visto, parola chiave 'tkwikibrowser' 'TouchGraphWikiBrowser', dove gli elementi sono combinati con un tipo di elastico, ma sono come magneti dello stesso pol.

Non so quale sarebbe la meccanica, inserendo il tuo caso, ma forse 'caso' è la parola chiave giusta: gli elementi sono messi in un caso, e vengono allontanati dal confine del caso, e spingere via l'un l'altro, molto di più, se hanno più attributi in comune.

Iniziano in posizioni casuali e si spostano in dipendenza della distanza dal muro, e alla distanza da elementi simili, e cercano una posizione stabile.

La formula per allontanarsi a vicenda potrebbe essere lineare o quadratica rispetto alla distanza e puoi cercare una buona formula dal vivo, manipolando i valori.

Aggiornamento:

Per il potere attrattivo, potresti semplicemente assumere l'inverso del potere distraente. Quindi se 2 elementi condividono non un singolo attributo, questa sarebbe la massima attrazione.

Usa un casuale casuale, o ordina per un hash dei dati concatenati: un buon hash fornisce output molto dissimili per input simili, quindi le voci che sono simili in qualsiasi dimensione dovrebbero essere separate.