python - 列表中每个字符串至少包含三个字符的最短唯一组合

Question

我想为字符串列表中的每个元素找到最短的唯一字符组合。每个组合应至少由字符串的第一个字符及其两个最稀有的字符组成(如有必要，则更多)并且顺序很重要。如果一个字符在一个字符串中出现多次，它应该获得更大的权重。

考虑以下示例:

liste = ["apple", "pear", "banana", "xylophone", "bear", "banunu"]
combinations = ["apl", "per", "ban", "xyh", "ber", "bnu"

对于 apple，p 和 e 总共出现了 4 次，但由于 p 在 apple，应该组合使用。

用 python 编写此逻辑最有效的方法是什么？

Answer 1

你可以这样做:

import heapq

from collections import Counter
from operator import itemgetter


def combination(word, n, counts):
    word_count = Counter(word)
    elements = []
    seen = set()
    for i, c in enumerate(word[1:]):
        if c not in seen:
            elements.append((-1 * counts[c], word_count[c], i, c))
            seen.add(c)
    top = heapq.nlargest(n, elements)
    characters = map(itemgetter(3), top)

    return word[0] + ''.join(sorted(characters, key=lambda x: word.index(x)))


lst = ["apple", "pear", "banana", "xylophone", "bear", "banunu"]

counts = Counter(''.join(lst))

result = [combination(w, 2, counts) for w in lst]
print(result)

输出

['apl', 'per', 'ban', 'xyh', 'ber', 'bnu']

这个想法是创建一个代表每个唯一字母的优先级标准的元组。所以 elements 是一个包含元组的列表，表示:

1. counts[c]:总体计数(因为您希望最稀有的乘以 -1)
2. word_count[c]:单词中字母的具体数量
3. i:代表字母的第一个位置
4. c:字母本身。

创建列表元素后:

elements = []
seen = set()
for i, c in enumerate(word[1:]):
    if c not in seen:
        elements.append((-1 * counts[c], word_count[c], i, c))
        seen.add(c)

请注意，由于字符必须是唯一的，因此我们使用一组 (seen) 来保证唯一性。最后你使用 heapq.nlargest根据上述条件获取前 n 个元素。