最短独特组合列表中每个字符串至少包含三个字符的组合

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后：

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元素。你知道吗