Dividing list of integers into alternating groups of even and odd sums

Question

Ok so lets pretend we have a list [1, 3, 5, 7, 9, 11, 13], I want to make a python program which will divide the list into the maximum number of groups alternating between sums of even or odd. (Even always has to go first) For example the list above can be divided into:

[1,3] , [5,7,9] , [11,13] even , odd, , even

If the list was: [11, 2, 17, 13, 1, 15, 3] we would have:

[2], [11], [13,1], [15], [17,3]

This way, we cannot further divide, and we have the maximum number of groups. I have been thinking about various solutions, for example putting the evens first and then continuing with the groupings. My code so far divides the list of all the integers into a list of even integers and a list of odd integers.

Does anyone have any ideas on how to use the number of even and odd integers to calculate how many even and odd groups there should be in the final list.

Edit: The list can have any numbers less than 100 as long as they don't repeat, they are not necessarily consecutive.

this is the structure I've been trying to use so far (its incomplete but you can look at it)

while True:
itera = []
if count % 2 == 0 and len(evens) > 0:
    x = evens[0]
    itera.append(x)
    lines.append(itera)
    evens.remove(x)
if count % 2 == 1 and len(odds) > 0:
    x = odds[0]
    itera.append(x)
    lines.append(itera)
    odds.remove(x)
if len(odds) == 0:
    if count % 2 == 1:
        print(count+1)

if len(evens) == 0:
    if count % 2 == 0:

    if count % 2 == 1 and len(odds) :
        print(count+1)
        
count+=1
if len(breeds) == 0:
    break

Really appreciated if someone could help out

Answer 1

After a few failures, I think I finally understand the problem and I think I have it. There are unsolvable cases for lists shorter than 4 elements, so the code below only tests cases with 4 elements and higher.

The first two test cases are the two presented at the top of the question. The next two test the two trivially degenerate cases...longer lists of all even or all odd values. Then I do some random tests.

For the random tests, I try one list of each length from 4 to 14. This doesn't necessarily test all the possible cases, because each case depends on the mix of even odd numbers, but it has a good chance to. Also, you can run this over and over, and you get different results each time, but the results always seem to be correct.

import random

def do_it(input):

    print(input, ":\n    ", end="")

    r = []

    # Split the input into two groups, odds and evens
    odds = [n for n in input if n % 2]
    evens = [n for n in input if not n % 2]

    # First, add all of the trivial pairings of a single even and a single odd while we
    # still have one of each kind
    while len(odds) and len(evens):
        r.append([evens.pop(0)])
        r.append([odds.pop(0)])

    if len(odds):
        # If we now only have odd numbers...

        # Add trivial pairs of even then odd sums while we have 3 or more values
        while len(odds) > 2:
            r.append([odds.pop(0), odds.pop(0)])
            r.append([odds.pop(0)])
        if len(odds) == 2:
            # If we have two left over values, we're good, just create a final pair that will be even
            r.append([odds.pop(0), odds.pop(0)])
        elif len(odds):
            # We only have one odd. This is the strange case.  Here, we collapse the second and third
            # to last entries, which we can do because one of them is even and so the result will stay odd
            r[-3].extend(r.pop(-2))
            # Now the last entry is wrong because it is even but should now be odd.  But hey, we have one
            # last odd that we can add to it to change it from even to odd!  So we just do that.
            r[-1].append(odds.pop(0))
    elif len(evens):
        # If we now only have even numbers...

        # Add one last even value to the end of the list
        r.append([evens.pop(0)])
        # Now add the remaining evens to the last list.  We could add them to any of the
        # lists (or multiple lists), but just the last one is as good a choice as any.
        while len(evens):
            r[-1].append(evens.pop(0))

    print(r, "  (", len(r), ")")
    return r

print("Test cases given in question...")
do_it([1, 3, 5, 7, 9, 11, 13])
do_it([11, 2, 17, 13, 1, 15, 3])
print()

print("Trivially degenerate cases...")
do_it([1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35])
do_it([2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30])
print()

print("Random cases of increasing list length...")
for i in range(4, 15):
    do_it(random.sample(range(1, 100), i))

Sample run results:

Test cases given in question...
[1, 3, 5, 7, 9, 11, 13] :
    [[1, 3], [5, 7, 9], [11, 13]]   ( 3 )
[11, 2, 17, 13, 1, 15, 3] :
    [[2], [11], [17, 13], [1], [15, 3]]   ( 5 )

Trivially degenerate cases...
[1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35] :
    [[1, 3], [5], [7, 9], [11], [13, 15], [17], [19, 21], [23], [25, 27], [29], [31, 33], [35]]   ( 12 )
[2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30] :
    [[2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30]]   ( 1 )

Random cases of increasing list length...
[14, 61, 88, 92] :
    [[14], [61], [88, 92]]   ( 3 )
[38, 98, 77, 87, 76] :
    [[38], [77], [98], [87], [76]]   ( 5 )
[71, 51, 45, 86, 56, 22] :
    [[86], [71], [56], [51], [22], [45]]   ( 6 )
[87, 16, 27, 52, 65, 77, 45] :
    [[16], [87], [52], [27], [65, 77], [45]]   ( 6 )
[84, 27, 13, 51, 58, 12, 46, 7] :
    [[84], [27], [58], [13], [12], [51], [46], [7]]   ( 8 )
[1, 65, 22, 41, 56, 18, 38, 69, 75] :
    [[22], [1], [56], [65], [18], [41, 38], [69, 75]]   ( 7 )
[34, 57, 18, 35, 40, 50, 43, 26, 44, 27] :
    [[34], [57], [18], [35], [40], [43], [50], [27], [26, 44]]   ( 9 )
[53, 47, 18, 17, 79, 36, 42, 31, 73, 92, 25] :
    [[18], [53], [36], [47], [42], [17], [92], [79], [31, 73], [25]]   ( 10 )
[19, 95, 35, 76, 60, 57, 58, 98, 46, 77, 26, 85] :
    [[76], [19], [60], [95], [58], [35], [98], [57], [46], [77], [26], [85]]   ( 12 )
[23, 86, 98, 56, 92, 82, 37, 36, 85, 12, 89, 94, 81] :
    [[86], [23], [98], [37], [56], [85], [92], [89], [82], [81], [36, 12, 94]]   ( 11 )
[86, 79, 74, 42, 50, 80, 75, 40, 97, 54, 66, 70, 60, 39] :
    [[86], [79], [74], [75], [42], [97], [50], [39], [80, 40, 54, 66, 70, 60]]   ( 9 )