问列表中具有权重的字母重复组合
EN

Stack Overflow用户

提问于 2017-12-07 00:15:01

回答 4查看 312关注 0票数 0

我有四个字母有不同的重量

letters = ['C', 'N', 'O', 'S']
weights_of_l = [1, 1, 2, 2]

我想得到字母的组合，其中的weight = 2。这封信可以反复挑选，顺序也不重要。结果可以是列表或数组，也可以是任何窗体，但可以使用此组合。

comb_w2 = ['CC','NN','NC','O','S']

在这里，C和N有weight = 1，所以组合两个字母有weight = 2：可能的组合是'CC','NN','NC'

O和S已经有了weight = 2，所以不能与其他字母结合。有计算这个的库吗？我看到了itertools，但它只给出了可能性的数量，而没有给出组合。

python

python-2.7

combinations

回答 4

Stack Overflow用户

发布于 2017-12-07 00:38:35

你的问题是分区 (不容易)。您可以使用这 post为给定的权重生成所有可能的组合结果。然后，您可以删除包含在weights_of_l中没有的键的那些。最后，用字母替换数字，并为具有相同权重的字母创建排列。

票数 2

Stack Overflow用户

发布于 2017-12-07 00:54:24

@Sneha有一个很好且简洁的答案，但是如果你要有很多组合，那么最好不要在创建组合方面走得太远。此解决方案更长，但对于目标得分较高的长字母列表，运行速度更快：

letters = ['C', 'N', 'O', 'S']
weights_of_l = [1, 1, 2, 2]

def get_combos(letters, weights, goal):
    weighted_letters = list(zip(letters, weights))
    combos = set()

    def get_combos(letters, weight):
        for letter, next_weight in weighted_letters:
            total = weight + next_weight
            if total == goal:
                combos.add(''.join(sorted(letters + letter)))
            elif total > goal:
                pass
            else:
                get_combos(letters + letter, weight+next_weight)

    get_combos('',0)
    return combos

print(get_combos(letters, weights_of_l, 3))

编辑:我认为这个可能会更快：

letters = ['C', 'N', 'O', 'S']
weights_of_l = [1, 1, 2, 2]

def get_combos(letters, weights, goal):
    weighted_letters = sorted(zip(weights, letters))
    combos = []

    def get_combos(letters, weight, weighted_letters):
        for i, (next_weight, letter) in enumerate(weighted_letters):
            total = weight + next_weight
            if total == goal:
                combos.append(letters + letter)
            elif total > goal:
                return
            else:
                get_combos(letters+letter, weight+next_weight, weighted_letters[i:])

    get_combos('',0,weighted_letters)
    return combos

print(get_combos(letters, weights_of_l, 3))

票数 1

Stack Overflow用户

发布于 2017-12-07 00:35:23

创建字母的所有组合，并使用筛选函数删除不等于2的所有组合。

from itertools import combinations_with_replacement
letters = ['C', 'N', 'O', 'S']
weights_of_l = [1, 1, 2, 2]
y=dict(zip(letters,weights_of_l))   #Creates a dict of the two list letters 
#and weights_of_l
print(list(map(lambda x:''.join(x),filter(lambda 
x:y[x[0]]+y[x[1]]==2,combinations_with_replacement(letters,2)))))