I have two list with values: list1 = [3,4,5,6,7,8] and list2 = [8,9,10,12,14,16,18,20]. i want to compare each value from list1 with each value from list2 and if their sum is even, I want to add the value from list2 to another list: list3. HOWEVER. I don't want too many similar values in list3. So, once value from list2 is included to list3, I don't want it to be used anymore, UNLESS there is no other option.

So in this example the output would be: [9, 8, 8, 10, 9, 12]. as you see, 8 was added again only because no other value from list2 summed up to even number with 5. same thing with 7 from list1, but since 8 from list2 was already used two times it uses 9 instead.

How could i do that? Is there better solution to get desired output?

CodePudding user response：

If your condition is only for the "sum being even", then as @jl-peyret suggested, you can partition the list and efficiently create your resulting list in O(len(list1) len(list2)) time.

If the condition is something generic, then here's a generic method to generate the result -

def condition(x, y):
    # sum is even
    return not bool((x   y) % 2)

def get_default(list2, current_default, used):
    # get next default value, in case none of the values match condition
    # TODO: for OP to implement
    return list2[0], current_default

list1 = [3,4,5,6,7,8]
list2 = [8,9,10,12,14,16,18,20]
list3 = []

used = [False] * len(list2)  # for keeping track of used items in list2
current_default = [0, 0] # index, and count of times the value is used

for i, num1 in enumerate(list1):
    # check if condition is true for any item in list2 which is not used yet
    for j, num2 in enumerate(list2):
        if not used[j] and condition(num1, num2):
            list3.append(num2)
            used[j] = True
            break

    # if none of the items in list2 match with the condition, use default logic
    if len(list3) < i   1:
        val, current_default = get_default(list2, current_default, used)
        list3.append(val)

print(list3)

this prints

[9, 8, 8, 10, 8, 12]

Currently, the get_default() is using list2[0] as default value in case no item is found in list2 matching given condition. I will leave implementing the get_default() to you, it should be trivial to implement it given your condition that a value can be used twice at max with the help of tracking pointer current_default.

For generic condition, I don't think there is a way to do it more efficiently than O(n^2) but you can do a further optimisation to use a linked list instead of list for list2 and shorten the search space for used values where we are doing the condition matching.

CodePudding user response：

To get the expected output listed in the question, the following code iterates through the first list checking each number against the numbers in the second list until an even sum is found that has not yet been added to the third list. Once found, it is added, but if a repetition becomes necessary, then a counter dictionary is used to add the first number from the second list which has been repeated in the third list the least.

def listComp(list1, list2):
    list3 = []
    for list1NUM in list1:
        preList = []
        for list2NUM in list2:
            if (list1NUM   list2NUM) % 2 == 0:
                preList.append(list2NUM)
        postList = []
        for prelistNum in preList:
            if prelistNum not in list3:
                list3.append(prelistNum)
                break
            else:
                postList.append(prelistNum)
        if len(preList) == len(postList):
            from collections import Counter
            itemCount = Counter(list3)
            list3.append(min(itemCount, key=itemCount.get))
    return list3
list1 = [3,4,5,6,7,8]
list2 = [8,9,10,12,14,16,18,20]
list3 =  listComp(list1, list2)
print (list3)

The preceding code produces the following output:

[9, 8, 8, 10, 9, 12]