分群問題.md

分群問題

某一行中的字母，如果有在其他行也出現，則將他們合併為一行。

例如:

A B
C A
D C
E F
N G
C N

結果:

A B C D N G
E F

問題

問題出自 segmentfault, by biopython

回答

這種 partition 的問題可以用 graph 來解決, 但我在這裡不想要用 graph, 所以改用兩個 dictionary 來替代:

char2id = {}
id2charset = {}

def getcharset(c):
    try:
        return id2charset[char2id[c]]
    except:
        return None

def newcharset(chars):
    newset = set(chars)
    return newset

def merge(charset1, charset2):
    if id(charset1)==id(charset2):
        return
    charset1 |= charset
    for c in charset2:
        char2id[c] = id(charset1)
    id2charset.pop(id(charset2))

with open('test') as reader:
    for line in reader:
        chars = line.strip().split()
        newset = newcharset(chars)
        id2charset[id(newset)] =newset

        for c in chars:
            charset = getcharset(c)
            if charset:
                merge(newset, charset)
            else:
                char2id[c] = id(newset)

with open('report', 'w') as writer:
    for id, charset in id2charset.items():
        print(' '.join(charset), file=writer)

上述代碼可以完成工作不過只保證分群的正確而不保證順序。

測試資料 test:

A B
C A
D C
E F
N G
C N
X Y
F P
P Q
X Z

結果:

P E Q F
X Y Z
B D C G N A

檢查正確性的方法很簡單, 因為這種合併的規則會導致最後每個字母只會在整個文件中出現一次(出現兩次以上代表有該 merge 的沒 merge)

下面是簡單地用 Counter 寫了一個檢查的 script:

from collections import Counter

with open('report', 'r') as reader:
    ct = Counter()
    for line in reader:
        ct += Counter(line.strip().split())

for item, count in ct.most_common():
    if count <= 1:
        break
    print(item, count)