过滤一组匹配的字符串排列
Filter a Set for Matching String Permutations
我正在尝试使用 itertools.permutations() 来 return string 的所有排列和return 仅属于一组 个单词。
import itertools
def permutations_in_dict(string, words):
'''
Parameters
----------
string : {str}
words : {set}
Returns
-------
list : {list} of {str}
Example
-------
>>> permutations_in_dict('act', {'cat', 'rat', 'dog', 'act'})
['act', 'cat']
'''
我当前的解决方案在终端中运行良好,但不知何故无法通过测试用例...
return list(set([''.join(p) for p in itertools.permutations(string)]) & words)
任何帮助将不胜感激。
显然您希望输出按字母顺序排序,所以应该这样做:
return sorted(set(''.join(p) for p in itertools.permutations(string)) & words)
试试这个解决方案
list(map("".join, itertools.permutations('act')))
['act', 'atc', 'cat', 'cta', 'tac', 'tca']
我们可以称它为listA
listA = list(map("".join, itertools.permutations('act')))
您的列表是 ListB
listB = ['cat', 'rat', 'dog', 'act']
然后使用集合交集
list(set(listA) & set(listB))
['cat', 'act']
您可以简单地使用 collections.Counter()
将 words
与 string
进行比较,而无需创建所有 permutations
(这会随着字符串的长度而增加):
from collections import Counter
def permutations_in_dict(string, words):
c = Counter(string)
return [w for w in words if c == Counter(w)]
>>> permutations_in_dict('act', {'cat', 'rat', 'dog', 'act'})
['cat', 'act']
注意:set
s 是无序的,所以如果您需要特定的顺序,您可能需要对结果进行排序,例如return sorted(...)
问题类别
您要解决的问题最好描述为测试 anagram 个匹配项。
使用排序的解决方案
traditional solution是对目标字符串进行排序,对候选字符串进行排序,判断是否相等
>>> def permutations_in_dict(string, words):
target = sorted(string)
return sorted(word for word in words if sorted(word) == target)
>>> permutations_in_dict('act', {'cat', 'rat', 'dog', 'act'})
['act', 'cat']
使用多重集的解决方案
另一种方法是使用collections.Counter() to make a multiset 相等性测试。这在算法上优于排序解决方案(O(n)
对比 O(n log n)
)但往往会失败,除非字符串的大小很大(由于散列所有字符的成本)。
>>> def permutations_in_dict(string, words):
target = Counter(string)
return sorted(word for word in words if Counter(word) == target)
>>> permutations_in_dict('act', {'cat', 'rat', 'dog', 'act'})
['act', 'cat']
使用完美哈希的解决方案
一个独特的字谜签名或perfect hash可以通过将字符串中每个可能的字符对应的素数相乘来构造。
commutative property of multiplication guarantees that the hash value will be invariant for any permutation of a single string. The uniqueness of the hash value is guaranteed by the fundamental theorem of arithmetic(也称为唯一质因数分解定理)。
>>> from operator import mul
>>> primes = [2, 3, 5, 7, 11]
>>> primes += [p for p in range(13, 1620) if all(pow(b, p-1, p) == 1 for b in (5, 11))]
>>> anagram_hash = lambda s: reduce(mul, (primes[ord(c)] for c in s))
>>> def permutations_in_dict(string, words):
target = anagram_hash(string)
return sorted(word for word in words if anagram_hash(word) == target)
>>> permutations_in_dict('act', {'cat', 'rat', 'dog', 'act'})
['act', 'cat']
使用排列的解决方案
当字符串较小时,使用 itertools.permutations() 在目标字符串上按排列搜索是合理的(在 n 长度字符串上生成排列会生成 n 阶乘候选)。
好消息是当n小而words的数量大时,这种方法运行s非常快(因为集合成员测试是 O(1)):
>>> from itertools import permutations
>>> def permutations_in_dict(string, words):
perms = set(map(''.join, permutations(string)))
return sorted(word for word in words if word in perms)
>>> permutations_in_dict('act', {'cat', 'rat', 'dog', 'act'})
['act', 'cat']
正如 OP 推测的那样,使用 set.intersection():
可以将纯 python 搜索循环加速到 c-speed
>>> def permutations_in_dict(string, words):
perms = set(map(''.join, permutations(string)))
return sorted(words & perms)
>>> permutations_in_dict('act', {'cat', 'rat', 'dog', 'act'})
['act', 'cat']
最佳解决方案
哪种解决方案最好取决于 string 的长度和 words 的长度。时间将显示哪个最适合特定问题。
以下是使用两种不同字符串大小的各种方法的一些时间比较:
Timings with string_size=5 and words_size=1000000
-------------------------------------------------
0.01406 match_sort
0.06827 match_multiset
0.02167 match_perfect_hash
0.00224 match_permutations
0.00013 match_permutations_set
Timings with string_size=20 and words_size=1000000
--------------------------------------------------
2.19771 match_sort
8.38644 match_multiset
4.22723 match_perfect_hash
<takes "forever"> match_permutations
<takes "forever"> match_permutations_set
结果表明,对于小字符串,最快的方法使用交集搜索目标字符串的排列。
对于较大的字符串,最快的方法是传统的排序和比较解决方案。
希望您和我一样发现这个小小的算法研究很有趣。要点是:
- 集合、itertools 和集合可以快速解决此类问题。
- Big-oh 运行ning 时间很重要(n 阶乘分解为大 n)。
- 恒定的开销很重要(由于散列开销,排序胜过多重集)。
- 离散数学是思想的宝库。
- 除非您进行分析和 运行 时间安排,否则很难知道什么是最好的 :-)
计时设置
FWIW,这是我用来 运行 比较时间的测试设置:
from collections import Counter
from itertools import permutations
from string import letters
from random import choice
from operator import mul
from time import time
def match_sort(string, words):
target = sorted(string)
return sorted(word for word in words if sorted(word) == target)
def match_multiset(string, words):
target = Counter(string)
return sorted(word for word in words if Counter(word) == target)
primes = [2, 3, 5, 7, 11]
primes += [p for p in range(13, 1620) if all(pow(b, p-1, p) == 1 for b in (5, 11))]
anagram_hash = lambda s: reduce(mul, (primes[ord(c)] for c in s))
def match_perfect_hash(string, words):
target = anagram_hash(string)
return sorted(word for word in words if anagram_hash(word) == target)
def match_permutations(string, words):
perms = set(map(''.join, permutations(string)))
return sorted(word for word in words if word in perms)
def match_permutations_set(string, words):
perms = set(map(''.join, permutations(string)))
return sorted(words & perms)
string_size = 5
words_size = 1000000
population = letters[: string_size+2]
words = set()
for i in range(words_size):
word = ''.join([choice(population) for i in range(string_size)])
words.add(word)
string = word # Arbitrarily search use the last word as the target
print 'Timings with string_size=%d and words_size=%d' % (string_size, words_size)
for func in (match_sort, match_multiset, match_perfect_hash, match_permutations, match_permutations_set):
start = time()
func(string, words)
end = time()
print '%-10.5f %s' % (end - start, func.__name__)
为什么还要费心排列?如果您将单词视为字母词典,这将是一个简单得多的问题。我确信有比这更好的理解,但是:
letters = dict()
for i in word:
letters[i] = letters.get(i, 0) + 1
对单词执行此操作,然后对集合中的每个单词执行此操作,确保每个键的值大于或等于该单词的键的值。如果是,请将其添加到您的输出中。
额外的好处:如果您的单词列表非常长,这应该很容易并行化。
我正在尝试使用 itertools.permutations() 来 return string 的所有排列和return 仅属于一组 个单词。
import itertools
def permutations_in_dict(string, words):
'''
Parameters
----------
string : {str}
words : {set}
Returns
-------
list : {list} of {str}
Example
-------
>>> permutations_in_dict('act', {'cat', 'rat', 'dog', 'act'})
['act', 'cat']
'''
我当前的解决方案在终端中运行良好,但不知何故无法通过测试用例...
return list(set([''.join(p) for p in itertools.permutations(string)]) & words)
任何帮助将不胜感激。
显然您希望输出按字母顺序排序,所以应该这样做:
return sorted(set(''.join(p) for p in itertools.permutations(string)) & words)
试试这个解决方案
list(map("".join, itertools.permutations('act')))
['act', 'atc', 'cat', 'cta', 'tac', 'tca']
我们可以称它为listA
listA = list(map("".join, itertools.permutations('act')))
您的列表是 ListB
listB = ['cat', 'rat', 'dog', 'act']
然后使用集合交集
list(set(listA) & set(listB))
['cat', 'act']
您可以简单地使用 collections.Counter()
将 words
与 string
进行比较,而无需创建所有 permutations
(这会随着字符串的长度而增加):
from collections import Counter
def permutations_in_dict(string, words):
c = Counter(string)
return [w for w in words if c == Counter(w)]
>>> permutations_in_dict('act', {'cat', 'rat', 'dog', 'act'})
['cat', 'act']
注意:set
s 是无序的,所以如果您需要特定的顺序,您可能需要对结果进行排序,例如return sorted(...)
问题类别
您要解决的问题最好描述为测试 anagram 个匹配项。
使用排序的解决方案
traditional solution是对目标字符串进行排序,对候选字符串进行排序,判断是否相等
>>> def permutations_in_dict(string, words):
target = sorted(string)
return sorted(word for word in words if sorted(word) == target)
>>> permutations_in_dict('act', {'cat', 'rat', 'dog', 'act'})
['act', 'cat']
使用多重集的解决方案
另一种方法是使用collections.Counter() to make a multiset 相等性测试。这在算法上优于排序解决方案(O(n)
对比 O(n log n)
)但往往会失败,除非字符串的大小很大(由于散列所有字符的成本)。
>>> def permutations_in_dict(string, words):
target = Counter(string)
return sorted(word for word in words if Counter(word) == target)
>>> permutations_in_dict('act', {'cat', 'rat', 'dog', 'act'})
['act', 'cat']
使用完美哈希的解决方案
一个独特的字谜签名或perfect hash可以通过将字符串中每个可能的字符对应的素数相乘来构造。
commutative property of multiplication guarantees that the hash value will be invariant for any permutation of a single string. The uniqueness of the hash value is guaranteed by the fundamental theorem of arithmetic(也称为唯一质因数分解定理)。
>>> from operator import mul
>>> primes = [2, 3, 5, 7, 11]
>>> primes += [p for p in range(13, 1620) if all(pow(b, p-1, p) == 1 for b in (5, 11))]
>>> anagram_hash = lambda s: reduce(mul, (primes[ord(c)] for c in s))
>>> def permutations_in_dict(string, words):
target = anagram_hash(string)
return sorted(word for word in words if anagram_hash(word) == target)
>>> permutations_in_dict('act', {'cat', 'rat', 'dog', 'act'})
['act', 'cat']
使用排列的解决方案
当字符串较小时,使用 itertools.permutations() 在目标字符串上按排列搜索是合理的(在 n 长度字符串上生成排列会生成 n 阶乘候选)。
好消息是当n小而words的数量大时,这种方法运行s非常快(因为集合成员测试是 O(1)):
>>> from itertools import permutations
>>> def permutations_in_dict(string, words):
perms = set(map(''.join, permutations(string)))
return sorted(word for word in words if word in perms)
>>> permutations_in_dict('act', {'cat', 'rat', 'dog', 'act'})
['act', 'cat']
正如 OP 推测的那样,使用 set.intersection():
可以将纯 python 搜索循环加速到 c-speed>>> def permutations_in_dict(string, words):
perms = set(map(''.join, permutations(string)))
return sorted(words & perms)
>>> permutations_in_dict('act', {'cat', 'rat', 'dog', 'act'})
['act', 'cat']
最佳解决方案
哪种解决方案最好取决于 string 的长度和 words 的长度。时间将显示哪个最适合特定问题。
以下是使用两种不同字符串大小的各种方法的一些时间比较:
Timings with string_size=5 and words_size=1000000
-------------------------------------------------
0.01406 match_sort
0.06827 match_multiset
0.02167 match_perfect_hash
0.00224 match_permutations
0.00013 match_permutations_set
Timings with string_size=20 and words_size=1000000
--------------------------------------------------
2.19771 match_sort
8.38644 match_multiset
4.22723 match_perfect_hash
<takes "forever"> match_permutations
<takes "forever"> match_permutations_set
结果表明,对于小字符串,最快的方法使用交集搜索目标字符串的排列。
对于较大的字符串,最快的方法是传统的排序和比较解决方案。
希望您和我一样发现这个小小的算法研究很有趣。要点是:
- 集合、itertools 和集合可以快速解决此类问题。
- Big-oh 运行ning 时间很重要(n 阶乘分解为大 n)。
- 恒定的开销很重要(由于散列开销,排序胜过多重集)。
- 离散数学是思想的宝库。
- 除非您进行分析和 运行 时间安排,否则很难知道什么是最好的 :-)
计时设置
FWIW,这是我用来 运行 比较时间的测试设置:
from collections import Counter
from itertools import permutations
from string import letters
from random import choice
from operator import mul
from time import time
def match_sort(string, words):
target = sorted(string)
return sorted(word for word in words if sorted(word) == target)
def match_multiset(string, words):
target = Counter(string)
return sorted(word for word in words if Counter(word) == target)
primes = [2, 3, 5, 7, 11]
primes += [p for p in range(13, 1620) if all(pow(b, p-1, p) == 1 for b in (5, 11))]
anagram_hash = lambda s: reduce(mul, (primes[ord(c)] for c in s))
def match_perfect_hash(string, words):
target = anagram_hash(string)
return sorted(word for word in words if anagram_hash(word) == target)
def match_permutations(string, words):
perms = set(map(''.join, permutations(string)))
return sorted(word for word in words if word in perms)
def match_permutations_set(string, words):
perms = set(map(''.join, permutations(string)))
return sorted(words & perms)
string_size = 5
words_size = 1000000
population = letters[: string_size+2]
words = set()
for i in range(words_size):
word = ''.join([choice(population) for i in range(string_size)])
words.add(word)
string = word # Arbitrarily search use the last word as the target
print 'Timings with string_size=%d and words_size=%d' % (string_size, words_size)
for func in (match_sort, match_multiset, match_perfect_hash, match_permutations, match_permutations_set):
start = time()
func(string, words)
end = time()
print '%-10.5f %s' % (end - start, func.__name__)
为什么还要费心排列?如果您将单词视为字母词典,这将是一个简单得多的问题。我确信有比这更好的理解,但是:
letters = dict()
for i in word:
letters[i] = letters.get(i, 0) + 1
对单词执行此操作,然后对集合中的每个单词执行此操作,确保每个键的值大于或等于该单词的键的值。如果是,请将其添加到您的输出中。
额外的好处:如果您的单词列表非常长,这应该很容易并行化。