Algoritma "unsort" / homogenitas data

Dalam upaya untuk tidak menemukan kembali roda, saya bertanya apakah ada yang punya ide tentang algoritma homogenitas data. Contoh singkat:

Data saya mungkin memiliki beberapa elemen

1. Jumlah
2. Warna
3. Buah
4. Surat

Ada sekitar 100 elemen ini dalam sebuah array. Algoritma perlu mengurutkan elemen sehingga setiap entri 2 dengan nomor yang sama diberi jarak satu sama lain sebanyak mungkin, dan sama dengan warna, buah, dll. Ini juga akan menyenangkan jika saya dapat memprioritaskan elemen. Rasanya Anda tidak akan pernah mencapai 100% sehingga Anda akan memberikannya sejumlah pass untuk dilakukan, lihat hasilnya, lalu coba lebih banyak pass untuknya.

Saya tidak akan terkejut jika ada sesuatu di sini yang berfungsi yang saya tidak punya cukup google-fu untuk menemukannya.

Jenis ini menyadap saya untuk sementara waktu sehingga saya harus datang untuk melihat apakah itu sudah terpecahkan. Ini ideku. Dari awal, bukan aplikasi dari algoritma apa pun yang saya ketahui. Ini akan menjadi algoritma brute force yang agak mahal, tetapi harus cukup efektif. Itu dengan asumsi Anda berurusan dengan set data kecil yang Anda jelaskan (100 baris 4 kolom) dan bekerja pada komputer modern dengan ram yang cukup.

Tinjauan Umum : Kami menggunakan algoritme rekursif pada daftar yang disortir untuk membubarkan rekaman serupa dengan jarak maxiumumnya dalam rekaman serupa. Setelah setiap panggilan, semua catatan dengan orang tua yang sama berada pada jarak maksimum. Panggilan teratas mencakup semua catatan. Jadi itu dibatalkan dari dalam ke luar.

Struktur data :

• newIndexesadalah sebuah array<integer>. Indeks array adalah indeks baris yang ada. Nilai akan menjadi indeks baru, dimulai dengan -1
• dataadalah a array<array<string>>. Kuncinya adalah indeks, array dalam adalah representasi string dari nilai-nilai dalam satu baris. Tidak perlu menjadi string jika Anda memiliki cara pengelompokan data. Elemen array pertama adalah elemen dengan bobot terbesar.

Urutkan databerdasarkan urutan berat. Urutkan terlebih dahulu dengan kolom dengan bobot terbesar, di dalamnya dengan kolom dengan bobot terbesar ke-2, dll. Hasilnya adalah kebalikan dari apa yang Anda inginkan. Indeks berurutan.

Berikut ini adalah algorythm (dalam kode 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";
    } 

Kemudian terapkanIndeks baru ke data yang akan dibatalkan.

Pikiran tentang pendekatan: Tidak menguji ini, tetapi penyimpananindeks baru dan penyelesaian konflik mungkin bermasalah karena indeks pertama ditugaskan berdasarkan kolom paling tidak signifikan, jadi jika ada banyak konflik maka kolom signifikan lebih besar dapat mengelompok. Mungkin coba terapkan offset sebagai positif pertama, lalu negatif. Atau mungkin melakukannya semacam penyisipan dalam daftar tertaut, bukan array.

Itu mengingatkan saya pada beberapa algoritma jaringan yang saya lihat, kata kunci 'tkwikibrowser' 'TouchGraphWikiBrowser', di mana unsur-unsur digabungkan dengan semacam karet gelang, tetapi seperti magnet dari pol yang sama.

Saya tidak tahu apa yang akan menjadi mekanik, menarik dalam kasing Anda, tapi mungkin 'kasing' adalah kata kunci yang tepat: elemen dimasukkan ke kasing, dan didorong menjauh dari perbatasan kasing, dan saling mendorong satu sama lain , lebih dari itu, jika mereka memiliki banyak atribut yang sama.

Mereka mulai dalam posisi acak, dan bergerak dalam ketergantungan jarak ke dinding, dan ke jarak ke elemen serupa, dan mencari posisi stabil.

Rumus untuk mendorong satu sama lain bisa linear atau kuadrat ke kejauhan, dan Anda bisa mencari formula yang bagus secara langsung, dengan memanipulasi nilainya.

memperbarui:

Untuk kekuatan yang menarik, Anda bisa mengambil kebalikan dari kekuatan yang mengganggu. Jadi jika 2 Elemen berbagi bukan atribut tunggal, ini akan menjadi daya tarik maksimum.

Gunakan acak acak, atau urutkan berdasarkan hash dari data yang digabungkan: hash yang baik memberikan output yang sangat berbeda untuk input yang sama, sehingga entri yang serupa dalam dimensi apa pun harus dipisahkan.