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

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 是一个包含元组表示的列表：

counts[c]：总计数（你想要最稀有的乘以-1）
word_count[c]：单词中字母的具体个数
i：表示字母的第一个位置
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 个元素。

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

Shortest unique combination of at least three characters for each string in list

python

combinatorics