查找和分組字謎被Python

input: ['abc', 'cab', 'cafe', 'face', 'goo'] 
output: [['abc', 'cab'], ['cafe', 'face'], ['goo']]

的問題很簡單：它按字謎。訂單無關緊要。查找和分組字謎被Python

當然，我可以通過C++（這是我的母語）來做到這一點。但是，我想知道這可以在單行Python完成。 編輯：如果這是不可能的，也許2或3行。我是Python的新手。

要檢查兩個字符串是否是字謎，我使用排序。

>>> input = ['abc', 'cab', 'cafe', 'face', 'goo'] 
>>> input2 = [''.join(sorted(x)) for x in input] 
>>> input2 
['abc', 'abc', 'acef', 'acef', 'goo']

我認爲它可能是通過組合map左右是可行的。但是，我需要使用dict作爲哈希表。我不知道這是否可行。任何提示都會被理解！

來源

2011-11-18 Nullptr

你爲什麼要在_single line_中做這個？ –

這只是一種腦筋急轉彎。 – Nullptr

我編輯過。我想盡量減少代碼行數。 – Nullptr

一個可讀的一個在線解決方案：

output = [list(group) for key,group in groupby(sorted(words,key=sorted),sorted)]

例如：

>>> words = ['abc', 'cab', 'cafe', 'goo', 'face'] 
>>> from itertools import groupby 
>>> [list(group) for key,group in groupby(sorted(words,key=sorted),sorted)] 
[['abc', 'cab'], ['cafe', 'face'], ['goo']]

這裏的關鍵是使用itertools.groupby from the itertools module，它將把列表中的項目組合在一起。

我們提供給groupby的清單必須先進行排序，所以我們通過sorted(words,key=sorted)。這裏的訣竅是，sorted可以接受一個關鍵函數，並將根據此函數的輸出進行排序，因此我們再次將sorted作爲關鍵函數進行排序，這將按順序使用字符串的字母對這些字進行排序。沒有必要定義我們自己的功能或創建lambda。

groupby需要一個關鍵的功能，它用來告訴物品是否應該分組在一起，我們可以再次將它傳遞給內置的sorted函數。

最後要注意的是，輸出是成對的鍵和組對象，所以我們只取石斑對象並使用list函數將它們中的每一個都轉換爲列表。

（順便說一句 - 我不會打電話給你的變量input爲那麼你的隱藏the built-in input function，雖然這可能不是一個你應該使用。）

來源

2011-11-18 11:38:03

不適用於'['az'，'b'，'za']' – wutz

@wutz - 你是對的，它需要在最初的排序中處理長度將有loo –

@wutz - 現在通過將'sorted（words）'改爲'sorted（words，key = sorted）來修復' –

不是一個襯墊，但一個解決方案...

d = {} 
for item in input: 
    s = "".join(sorted(item)) 
    if not d.has_key(s): 
    d[s] = [] 
    d[s].append(item) 
input2 = d.values()

來源

2011-11-18 11:29:12 yurib

的可讀版本：

from itertools import groupby 
from operator import itemgetter 

def norm(w): 
    return "".join(sorted(w)) 

words = ['abc', 'cba', 'gaff', 'ffag', 'aaaa'] 

words_aug = sorted((norm(word), word) for word in words) 

grouped = groupby(words_aug, itemgetter(0)) 

for _, group in grouped: 
    print map(itemgetter(1), group)

一行程序：

print list(list(anagrams for _, anagrams in group) for _, group in groupby(sorted(("".join(sorted(word)), word) for word in words), itemgetter(0)))

打印：

[['aaaa'], ['abc', 'cba'], ['ffag', 'gaff']]

來源

2011-11-18 11:31:23 wutz

+1，我寧願使用'[[anagrams ...'而不是'list（list（anagrams' tho）以提高可讀性 – neurino

不可讀，一個在線解決方案：

>>> import itertools 
>>> input = ['abc', 'face', 'goo', 'cab', 'cafe'] 
>>> [list(group) for key,group in itertools.groupby(sorted(input, key=sorted), sorted)] 
[['abc', 'cab'], ['cafe', 'face'], ['goo']]

（當然，它確實是2號線如果算上進口...）

來源

2011-11-18 11:34:58

如果輸入中的anagrams不相鄰，則失敗 – wutz

@wutz：編輯答案糾正這個問題 –

from itertools import groupby 

words = ['oog', 'abc', 'cab', 'cafe', 'face', 'goo', 'foo'] 

print [list(g) for k, g in groupby(sorted(words, key=sorted), sorted)]

結果：

[['abc', 'cab'], ['cafe', 'face'], ['foo'], ['oog', 'goo']]

你不能只使用groupby函數，因爲它只能將你的關鍵函數產生相同結果的順序元素分組在一起。

簡單的解決方案就是首先使用與分組相同的功能對單詞進行排序。

來源

2011-11-18 11:41:56 Acorn

test with：' words = ['abc'，'caba']'... –

是的，忽略了，再加上單詞必須相鄰的事實。固定。 – Acorn

戴夫的答案很簡潔，但groupby所要求的排序是O(n log(n))操作。更快的解決方案是這樣的：

from collections import defaultdict 

def group_anagrams(strings): 
    m = defaultdict(list) 

    for s in strings: 
     m[tuple(sorted(s))].append(s) 

    return list(m.values())

來源

2017-06-03 14:43:46 kakarukeys

查找和分組字謎被Python

回答

相關問題