dize gruplama algoritması C#

Question

C# dizeleri için gruplandırma algoritması gibi bir şeye ihtiyacım var.

key|value 

"bla","AAA;BBB;CCC" // ';' is split sign 
"whatever","BBB;DDD;EEE;FF" 
"hmm", "ZZZ,YYY,XXX" 
"foo", "CCC,JJJ,VVV" 
.... 

: Böyle bir Dictonary

şey veri Ben belki var Ne (^^ hiçbir adjazenctmatrix) birisi :) sormalısınız gün ve ben delirmek önce denedik olduğunu (yeni bir sözlükte, neyse anahtar ... sayacı?)

"AAA;BBB;CCC;EEE;FF" (or without distinct to "AAA;BBB;CCC;BBB;DDD;EEE;FF") 

değer3 kendi grup

geçerli:

value1 ve value2 çok yeni bir dizeye grubu ilan "BBB" içerir

value4 contains "CCC" so group it to the others 
"AAA;BBB;CCC;EEE;FF;JJJ;VVV" (or without distinct to "AAA;BBB;CCC;BBB;DDD;EEE;FF;CCC;JJJ;VVV") 

SQL güncelleme için bu dizeyi ihtiyaç

güncelleme öğesi set grup = grup ('', '', ...)

Ben bölünmüş bunu ve katılmak çubuğu , bu bölüm Yani ilk verileri organize :-P

sayesinde

Answer 1

çalışır. Bir harita keys["bla"] = some_set("AAA", "BBB", "CCC"); ve benzeri var. Ardından, reverse["BBB"] = ["bla", "whatever"] gibi görünmesi gereken bir ters harita oluşturun. Her iki harita da orijinal verilerle aynı boyutta olmalıdır.

Sonra örtülü grafiğinde (yalancı kod) üzerinden bir DFS yapabilirsiniz:

merge = some_set() 
DFS(string key) { 
    if (key in merge) return; // Been here already. 
    merge.insert(key); 
    for (string edge : keys[key]) 
    for (string other_key : reverse[edge]) 
     DFS(other_key) 
} 

Yani artık DSF("bla") çağırabilir. Geri döndüğünde, "bla", "whatever", ..." ve grupta olabilecek diğer anahtarları içermeli ve istediğiniz sonucu elde etmek için dizelerini keys'dan bağlayabilirsiniz.

Her tuş aittir tüm grup için her tuş için DFS çağırabilir (karmaşıklık O (N^2 * set_op)). Ya da daha iyisi, daha önce üzerinde çalıştıkları tuşları tekrar takip etmekten kaçının (karmaşıklık O (N * set_op)).

Karma tabanlı ayarlar/haritalar kullanırsanız, set_op'unuz O(average string length)'dur. Ağaç tabanlı yapılar kullanırsanız, set_op O(logN)'dur. Çok uzun dizeleriniz veya çok fazla anahtarınız olmadığı sürece bunun önemi yok.