使用递归遍历列表

Question

我正在尝试使用递归来比较两个列表之间的元素值。对于 index i，if list1[i] = A and list2[i] = T反之亦然，这些值是有效的。此外，对于索引 i，if list1[i] = G and list2[i] = C反之亦然，这些值是有效的。但是，如果不满足这两个条件 ( list1[i] = A and list2[i] = G)，则这些值无效。我创建了两个新列表，其中有效值是存储，无效值被替换为空白 ''。这段代码在 for 循环 ( for i in range (0, len(list1)):) 中运行良好，但是如何使用递归呢？def check_valid(sequence1, sequence2): sequence1 = list(sequence1) sequence2 = list(sequence2) valid_units1 = [] valid_units2 = []    if (sequence1[i] == 'A' and sequence2[i] == 'T') or (sequence1[i] == 'T' and sequence2[i] == 'A'):        valid_units1.append(sequence1[i])        valid_units2.append(sequence2[i])    elif (sequence1[i] == 'G' and sequence2[i] == 'C') or (sequence1[i] == 'C' and sequence2[i] == 'G'):        valid_units1.append(sequence1[i])        valid_units2.append(sequence2[i])    else:        valid_units1.append(' ')        valid_units2.append(' ')    print(valid_units1)    print(valid_units2)    valid_units = [valid_units1, valid_units2]    return valid_units

Answer 1

如果您从两个列表开始并想逐个比较它们，您可以使用它zip()来简化您的生活。它会给你返回配对的元素。因此，如果您从两个列表开始，您可以zip：

list1 = ['A', 'T']

list2 = ['C', 'G']

zipped = list(zip(list1, list2))

# zipped is [('A', 'C'), ('T', 'G')]

#or use a list comprehension:

zipped = [pair for pair in  zip(list1, list2)]

zip()返回一个迭代器，这就是它被包裹在list()上面的原因。如果您在循环或其他需要交互器的情况下使用它，则不需要这样做。

如果你想比较这些，你可以使用一个字典来定义哪个字母映射到另一个，这将允许你编写一个更简单的测试函数：

# Define a mapping that describes which elements belong togethre

pairs = {

    'G':'T',

    'T':'G',

    'C':'A',

    'A':'C'

}

list1 = ['A', 'A', 'T', 'C', 'G', 'C', 'T', 'A']

list2 = ['C', 'G', 'G', 'A', 'C', 'A', 'C', 'T']

# make a new list if the pairs line up with the mapping:

legal = [(a, b) for a, b in  zip(list1, list2) if pairs[a] == b ]

# legal pairs: [('A', 'C'), ('T', 'G'), ('C', 'A'), ('C', 'A')]

没有太多理由递归地执行此操作，但您当然可以。由于zip()返回一个迭代器（pairs如下），您可以调用next()它以获取下一个值，然后将迭代器传回。当它没有项目时它会抛出一个StopIteration错误，所以这可能是递归的边缘条件：

def buildList(pairs, mapping):

    ''' Takes an iterator and mapping, returns a list of legal items defined by mapping '''

    try:

        a_pair = next(pairs)  # get first item from zipped list

    except StopIteration:   # no more items, just return an empty list

        return []

    a, b = a_pair            

    if mapping[a] == b:    

        return [(a, b)] + buildList(pairs, mapping)

    else: 

        return buildList(pairs, mapping)

list1 = ['A', 'A', 'T', 'C', 'G', 'C', 'T', 'A']

list2 = ['C', 'G', 'G', 'A', 'C', 'A', 'C', 'T']

pairs = {'G':'T','T':'G','C':'A','A':'C'}

buildList(zip(list1, list2), pairs) # use zip to make the zipped iterator

Answer 2

这个问题被标记为递归，这是我的看法 -

def head(xs = []):

  return xs[0]

def tail(xs = []):

  return xs[1:]

def check_pair(x = "", y = "", swap = True):

  if x == "A" and y == "C":

    return True

  elif x == "G" and y == "T":

    return True

  else:

    return swap and check_pair(y, x, False)

def check_valid(a = [], b = []):

  if (not a) or (not b):

    return

  elif check_pair(head(a), head(b)):

    yield (head(a), head(b))

    yield from check_valid(tail(a), tail(b))

  else:

    yield from check_valid(tail(a), tail(b))

a = ['A', 'A', 'T', 'C', 'G', 'C', 'T', 'A']

b = ['C', 'G', 'G', 'A', 'C', 'A', 'C', 'T']

print(list(check_valid(a,b)))

# [('A', 'C'), ('T', 'G'), ('C', 'A'), ('C', 'A')]

这很直观，但就像函数一样zip，该tail函数会创建中间值。我们可以通过使用一个简单的索引来减少内存需求，i-

def check_pair(x = "", y = "", swap = True):

  if x == "A" and y == "C":

    return True

  elif x == "G" and y == "T":

    return True

  else:

    return swap and check_pair(y, x, False)

def check_valid(a = [], b = [], i = 0):

  if i >= min(len(a), len(b)):

    return

  elif check_pair(a[i], b[i]):

    yield (a[i], b[i])

    yield from check_valid(a, b, i + 1)

  else:

    yield from check_valid(a, b, i + 1)

a = ['A', 'A', 'T', 'C', 'G', 'C', 'T', 'A']

b = ['C', 'G', 'G', 'A', 'C', 'A', 'C', 'T']

print(list(check_valid(a,b)))

# [('A', 'C'), ('T', 'G'), ('C', 'A'), ('C', 'A')]