按特定顺序递归随机排列列表

Question

我正在尝试按特定顺序递归地打乱列表。

我有：

def shuffle(list1, list2):
    a = []
    if len(list1) == 0:
        a += list2
        return a
    if len(list2) == 0:
        a += list1
        return a
    else:
        a += [list1[0]]
        list1.pop(0)
        a += [list2[0]]
        list2.pop(0)
    return a += shuffle(list1, list2)

Answer 1

您的核心问题是您没有返回递归调用。 清理代码中一些名义上未使用的局部变量可以得到：

def shuffle(list1, list2):
    a = []
    if len(list1) == 0:
        return list2
    if len(list2) == 0:
        return list1
    else:
        a.append(list1.pop(0))
        a.append(list2.pop(0))
    return a + shuffle(list1, list2)

当然，在上面的清理中，很明显你甚至不需要a累加器：

def shuffle(list1, list2):
    if len(list1) == 0:
        return list2
    if len(list2) == 0:
        return list1
    else:
        return [list1.pop(0),list2.pop(0)] + shuffle(list1, list2)

演示：

shuffle([1,2,3],[4,5,6])
Out[35]: [1, 4, 2, 5, 3, 6]
shuffle([1,2], [6,7,8,9])
Out[36]: [1, 6, 2, 7, 8, 9]

顺便说一句，这会改变输入列表，这通常是不可取的。 使用切片而不是关闭 ping 元素可能会更好地pop：

def shuffle(list1, list2):
    if len(list1) == 0:
        return list2
    if len(list2) == 0:
        return list1
    else:
        return [list1[0],list2[0]] + shuffle(list1[1:], list2[1:])

Answer 2

如何使用递归模型使此函数在这些情况下工作？

对于递归中两个列表不为空的每个步骤，您正在创建一个新的临时数组"a"，但随后没有对其进行任何操作。

您需要通过引用将存储结果的列表传递到递归链中（首选 - 它是零副本），或者在展开递归时返回列表片段并将其附加到结果数组中（功能，但每次都需要创建一个新的列表对象，这很慢）。

Answer 3

from itertools import chain
def shuffle(list1, list2):
    if len(list1)==len(list2): return list(chain(*zip(list1,list2)))
    # if the lists are of equal length, chaining the zip will be faster
    else:
        a = []
        while any([list1,list2]):
            for lst in (list1,list2):
                try: a.append(lst.pop(0))
                except IndexError: pass
        return a
    # otherwise, so long as there's items in both list1 and list2, pop the
    # first index of each (ignoring IndexError since one might be empty)
    # in turn and append that to a, returning the value when both lists are
    # empty.

这不是您要寻找的递归解决方案，但无论如何，显式解决方案通常更快，更容易阅读和调试。 @DSM指出，这可能是一道家庭作业题，所以我为误读道歉。我会继续留给它，以防它对任何人有启发。

Answer 4

生成器版本，只是因为生成器很棒^^

def shuffle(a,b):
    A = iter(a)
    B = iter(b)
    while True: 
        try:
            yield A.next()
        except StopIteration:
            for j in B: 
                yield j 
            break
        try:
            yield B.next()
        except StopIteration:
            for j in A:
                yield j
            break
print list(shuffle(a,b))