0

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.

Jan
  • 1,389
  • 4
  • 17
  • 43
  • A string inherently has an order. If the combination `{'N', 'C'}` is equivalent for your purposes to the combination `{'C', 'N'}` then using a set (as in this example) or another unambiguous notation would help clarify your question. – tripleee Dec 07 '17 at 08:31
  • If your real-life input set isn't a lot bigger than this, just generating all the possible permutations and filtering on their weight would seem like a straightforward and economical solution. – tripleee Dec 07 '17 at 08:33
  • @tripleee may you link the example? – Jan Dec 07 '17 at 08:33
  • 1
    Combinations, not permutations, sorry. [`itertools.combinations()`](https://docs.python.org/2/library/itertools.html#itertools.combinations) – tripleee Dec 07 '17 at 08:33

5 Answers5

2

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.

Juan Luis Ruiz-tagle
  • 318
  • 2
  • 8
1

@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))
Turksarama
  • 1,136
  • 6
  • 13
1

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)))
Reti43
  • 9,656
  • 3
  • 28
  • 44
  • I wonder there is any ways I can obtain weight in the result? It can be tuple or dictionary, just something like `[('CC',2),('NN',2),('NC',2),('O',2),('S',2)]` – Jan Dec 08 '17 at 06:12
  • @Jan You can trivially do that by yielding both the word and weight, e.g., `if weight == max_weight: yield ''.join(sorted(word)), weight` and later on `for result_word, result_weight in combinations(...): yield result_word, result_weight`. However, by definition all the results will have the same weight, so I see no point. – Reti43 Dec 08 '17 at 10:28
  • I plan to expand the code for larger data and do `weight <= max_weight` for upto result. Thanks so much. It works well and I learn so much more from this code. – Jan Dec 08 '17 at 11:54
0

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.

Sneha
  • 140
  • 6
0

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.

aprasanth
  • 1,079
  • 7
  • 20