将整数列表分成偶数和奇数的交替组

Question

好吧，让我们假设我们有一个列表 [1, 3, 5, 7, 9, 11, 13]，我想制作一个 python 程序，它将列表分成最大数量的组，在偶数或奇数和之间交替。（即使总是要先走）例如上面的列表可以分为：

[1,3] , [5,7,9] , [11,13] 偶数, 奇数, , 偶数

如果列表是： [11, 2, 17, 13, 1, 15, 3] 我们将有：

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

这样，我们不能进一步划分，并且我们有最大的组数。我一直在考虑各种解决方案，例如将偶数放在首位，然后继续分组。到目前为止，我的代码将所有整数列表分为偶数列表和奇数列表。

有没有人对如何使用偶数和奇数整数来计算最终列表中应该有多少偶数和奇数组有任何想法。

编辑：列表可以有任何小于 100 的数字，只要它们不重复，它们不一定是连续的。

这是到目前为止我一直在尝试使用的结构（它不完整，但你可以看看它）

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

如果有人可以帮忙，真的很感激

Answer 1

经过几次失败，我想我终于明白了问题所在，我想我已经明白了。对于短于 4 个元素的列表，存在无法解决的情况，因此下面的代码仅测试具有 4 个元素及更高元素的情况。

前两个测试用例是出现在问题顶部的两个测试用例。接下来的两个测试两个简单退化的情况......所有偶数或所有奇数的更长列表。然后我做一些随机测试。

对于随机测试，我尝试从 4 到 14 的每个长度的列表。这不一定测试所有可能的情况，因为每种情况取决于偶数奇数的混合，但它有很好的机会。此外，您可以一遍又一遍地运行它，每次都会得到不同的结果，但结果似乎总是正确的。

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))

示例运行结果：

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 )