CODEWITHSUNDEEP
pythonpython-2.7combinations
Jan
Jan

Reputation: 1479

Combinations with repetition of letters with weight from list

I have four letters with different weights as

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

I want to get the combinations of letters which weight = 2. The letter can be repeatedly chose and order is not important. The result can be list or array or any forms but with this combinations

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

Here C and N has weight = 1 so combining two letters have weight = 2: The possible combinations are 'CC','NN','NC'

O and S has weight = 2 already so it cannot combine with other letters. Is there any libraries for calculating this? I saw itertools but it gives only the number of possibility, not the combinations.

Upvotes: 0

Views: 512

Answers (5)

Turksarama
Turksarama

Reputation: 1136

@Sneha has a nice and succinct answer, but if you're going to have a lot of combinations then it might be better to to not go too far in creating combinations. This solution is longer but will run faster for long lists of letters with large goal scores:

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))

EDIT: I think this one might be even faster:

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))

Upvotes: 1

Reti43
Reti43

Reputation: 9797

My answer ended up being very similar to Turksarama's. Namely, if you need the combination of results, you have to sort the letters and use a set to get rid of the duplicates. My approach is more succinct, but requires calling set() with the function call.

letters = ['C', 'N', 'O', 'S']
weights = [1, 1, 2, 2]
items = list(zip(weights, letters))

def combinations(items, max_weight, weight=0, word=''):
    if weight == max_weight:
        yield ''.join(sorted(word))
    items_allowed = [(w, l) for w, l in items if max_weight - weight >= w]
    for w, l in items_allowed:
        for result in combinations(items_allowed, max_weight, weight+w, word+l):
            yield result

print(set(combinations(items, 2)))

Upvotes: 1

aprasanth
aprasanth

Reputation: 1099

Try the following code:

def find_combinations(letter_list, weight_list, weignt_sum):
    output_list = []
    letter_weight_dict = dict(zip(letter_list,weight_list))
    for key, val in letter_weight_dict.items():
        for key1, val1 in letter_weight_dict.items():
            if val+val1 == weignt_sum:
                if (key + key1)[::-1] not in output_list:
                    output_list.append(key+key1)
            if val == weignt_sum:
                output_list.append(key)
    return set(output_list)

letters = ['C', 'N', 'O', 'S']
weights_of_l = [1, 1, 2, 2]
combinations = find_combinations(letters, weights_of_l, 2)
print combinations

I got the following output:

['CC', 'S', 'NN', 'CN', 'O']

This may not be the best way to do this.

Upvotes: 0

Juan Luis Ruiz-tagle
Juan Luis Ruiz-tagle

Reputation: 341

Yours is a problem of partitioning (not easy stuff). You can use this post to generate all possible combination outcomes for a given weight. Then you can delete the ones that contain keys which you don't have in weights_of_l. Finally you substitute the numbers by the letters and create permutations for they letters that have the same weight.

Upvotes: 2

Sneha
Sneha

Reputation: 140

Create all combinations of the letters and use filter function to remove all combinations with combined weight not equal to 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)))))

Or you can initially filter all letters in the letters list to include those which has weight less than 2 or the weight you require and then create all combinations.

Upvotes: 0

Related Questions