How to find highest number from the vector provided?

user_10330908 0
Viewed 47

Say, a dictionary is provided with certain values. How to find the highest number ?

Input

d1 = {1: 1, 2: 6, 3: 7, 4: 1, 5: 3}
vector = 5

d1 = {1: 1, 2: 6, 3: 7, 4: 1, 5: 3}
vector = 5
l1 = list(td.values())

Based on vector value, it should print output. vector is 5, so sum of the dict-values to form vector is 3,1,1 Corresponding keys are 5,4,1 so, the output should be 541 but slight change here. Since value '1' is associated with multiple keys, it should pick up highest key, so, output should be 544 instead of 541 (For above input, to brief about combinations without considering '1+1+1+1+1' to '44444')

Another example

d1 = {1: 1, 2: 6, 3: 7, 4: 1, 5: 3}
  vector = 7
  Possible combinations:
  3  # --> Key of 7
  21 # --> Key of 6 & 1 (6+1 = 7)
  24 # --> Key of 6 & 1 (6+1 = 7)
  12 # --> Key of 1 & 6 (1+6 = 7)
  42 # --> Key of 1 & 6 (1+6 = 7)

  Output : 42 (Highest number)

Another

d1 = {1:9,2:4,3:2,4:2,5:6,6:3,7:2,8:2,9:1} 
vector = 5
here, it would be 1+2+2 (988). 
But, '1' can also be added 5 times to form vector 5, 
which would be '99999'

Since @Patrick Artner requested for minimal reproducible example, posting this though doesn't work as expected.

from itertools import combinations

def find_sum_with_index(l1, vector):
    index_vals = [iv for iv in enumerate(l1) if iv[1] < target]
    for r in range(1, len(index_vals) + 1):
        for perm in combinations(index_vals, r):
            if sum([p[1] for p in perm]) == target:
                yield perm


d1 = {1: 1, 2: 6, 3: 7, 4: 1, 5: 3}
vector=5
l1=list(d1.values())
for match in find_sum_with_index(l1, vector):
    print(dict(match))

Is there any specific algorithm to be chosen for these kind of stuffs ?
itertools python-3.x list dictionary
2 Answers

There are some steps involved, see documentation in comments in code:

d1 = {1: 1, 2: 6, 3: 7, 4: 1, 5: 3}
vector = 7

# create a dict that contains value -> sorted key-list, used to get final keys
from collections import defaultdict
d2 = defaultdict(list)
for k,v in d1.items():
    d2[v].append(k)
for k,v in d2.items():
    d2[k] = sorted(v, reverse=True) 

from itertools import chain, combinations
def powerset(iterable):
    "see itertools: powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

# create all combinations that sum to vector
p = [ s for s in powerset(d1.values()) if sum(s) == vector]

# sort combinations by length then value descending and take the max one
mp = max( (sorted(y, reverse=True) for y in p), key=lambda x: (len(x),x)) 

# get the correct keys to be used from d2 dict
rv = []
for num in mp:
    rv.append(d2[num][0])
    # remove used key from list
    d2[num][:] = d2[num][1:]

# sort by values, biggest first
rv.sort(reverse=True)

# solution
print(''.join(map(str,rv)))

For powerset - see itertools-recipes.

user_75053950

Similar to the other answer but allowing repeatedly using the same keys to get the max number of keys which values sum up to vector: 

d1 = {1: 1, 2: 6, 3: 7, 4: 1, 5: 3}
vector = 7

#create a dict that contains value -> max-key for that value
d2 = {}
for k,v in d1.items():
    d2[v] = max(d2.get(v,-1), k)

def mod_powerset(iterable,l):
    # uses combinations_with_replacement to allow multiple usages of one value
    from itertools import chain, combinations_with_replacement
    s = list(set(iterable))
    return chain.from_iterable(combinations_with_replacement(s, r) for r in range(l))

# create all combinations that sum to vector
p = [ s for s in mod_powerset(d1.values(),vector//min(d1.values())+1) if sum(s) == vector]
print(p)
# sort combinations by length then value descending and take the max one
mp = max( (sorted(y, reverse=True) for y in p), key=lambda x: (len(x),x)) 

# get the correct keys to be used from d2 dict
rv = [d2[num] for num in mp]

# sort by values, biggest first
rv.sort(reverse=True)

# solution
print(''.join(map(str,rv)))

Original powerset - see itertools-recipes.

user_75053950
Related