Find maximal weighted subset such that any two elements in subset do not sum to k

Question

The weight of the subset is the length of the value for each key.

Here is my attempt:

def nonDivisibleSubset(k, s):
    remdict={}
    result=[]
    for i in range(len(s)):
        rem=s[i]%k
        if rem not in remdict:
            remdict[rem]=[s[i]]
        else:
            remdict[rem].append(s[i])
    b=dict(sorted(remdict.items(), key= lambda x: len(x[1]), reverse=True))


Input: 
k=7
{2: [576, 338, 149, 702, 282, 436], 6: [496, 727, 209], 5: [278, 124], 4: [410, 718], 1: [771, 575]}

From this dictionary I want to append only the values of the keys 2,6,4 because 2+6!=7 and 2+4!=7 and 6+4!=7**

Why 2,4,6 and not 4,5,6? 4+5, 4+6 and 5+6 also all don't equal 7. — Błotosmętek, May 11 '20 at 10:09
Sorry, I forgot to add. The length of values should be the maximum. — vinoth s, May 11 '20 at 10:12
First thing that come to mind is maximal clique, where `(u,v)` is an edge if `u+v!=k`, but maximal clique is NP Hard, I hope there is a better solution... — amit, May 11 '20 at 10:15
The length of values of keys 4,5,6 is 7 while for 2,4,6 it is 11. So 2,4,6 should be chosen as it has the max length of values — vinoth s, May 11 '20 at 10:26

score 0 · Answer 1 · answered May 11 '20 at 11:52

so first of all - we need to find all different combinations, then find the maximal from them.

this is the code to find all different combinations:

def check(d, s, k):
        for i in d:
            if i + s == k:
                return False
        return True

for i in s:
    temp = [i]
    d = s.copy()
    d.pop(i)
    for j in d:
        if check(temp, j, k):
            temp.append(j)
     temp.sort()
        res_lst.append(temp)
    unique_data = [list(x) for x in set(tuple(x) for x in res_lst)]

(ref to how to find unique_data: Python: Uniqueness for list of lists)

to find the max subset:

res = []
res_sum = 0
for l in unique_data:
    tmp_sum = 0
    for n in l:
        tmp_sum += len(s[n])
    if tmp_sum > res_sum:
        res = l
        res_sum = tmp_sum
return res

score 0 · Answer 2 · answered May 12 '20 at 07:02

The idea is to group the numbers in s based on the remainders they give when divided by k and store the remainders as keys and their frequency/count as values. Then pick between max(key,k-key) and make sure you pick only one if key==0 or if key+key=k. There may be other ways to solve this as well without using dictionary.

def nonDivisibleSubset(k, s):
        remdict={}
        result=[]
        keyss=[]
        for i in range(len(s)):
            rem=s[i]%k
            if rem not in remdict:
                remdict[rem]=1
            else:
                remdict[rem]+=1
        #b=dict(sorted(remdict.items(), key= lambda x: len(x[1]), reverse=True))
        print(remdict)
        for key,value in remdict.items():
            if key==0:
                result.append(1)
            elif key+key==k:
                result.append(1)
            elif (k-key) in remdict.keys() and k-key not in keyss :
                print(max(remdict[key],remdict[k-key]))
                keyss.append(key)
                result.append(max(remdict[key],remdict[k-key]))
            elif (k-key) not in remdict.keys():
                print(remdict[key])
                result.append(remdict[key])
        print(result)
        return (sum(result))

Find maximal weighted subset such that any two elements in subset do not sum to k

2 Answers2