1

我需要从元组列表中生成一个列表：

a = [(1,2), (1,3), (2,3), (2,5), (2,6), (3,4), (3,6), (4,7), (5 6), (5,9), (5,10), (6,7)
             (6.10) (6.11) (7.8) (7.12) (8.12) (9.10) (10.11)]

规则是： - 我有来自任何 ( begin = random.choice (a)) 的记录 - 新列表中的项目必须具有以下关系：列表中每个元组的最后一项必须等于要插入的下一个元组的第一项。

有效输出示例（从元组 (3.1) 开始）：

[(3, 1), (1, 2), (2, 3), (3, 4), (4, 7), (7, 8), (8, 12), (12, 7), (7, 6), (6, 2), (2, 5), (5, 6), (6, 10), (10, 5) (5, 9), (9, 10), (10, 11), (11, 6), (6, 3)]

我怎样才能做到这一点？它使用列表推导吗？谢谢！

4

4 回答 4

0

在这里，lisb将按照您查找的顺序填充元组。当然，如果lisa提供了适当的元组（即，每个元组的第 1 个值与另一个元组的第 0 个值匹配）。无论实现如何，您的示例列表都将不起作用，因为所有值都不匹配（例如，没有第 0 个元素为 12，因此元组无法连接到任何其他元组）...所以你应该拿出一个更好的样本清单。

测试，工作。

import random

lisa = [(1, 2), (3, 4), (2, 3), (4, 0), (0, 9), (9, 1)]
lisb = []

current = random.choice(lisa)

while True:
    lisa.remove(current)
    lisb.append(current)
    current = next((y for y in lisa if y[0] == current[1]), None)
    if current == None:
        break

print lisb

如果您不想从中删除项目lisa，只需切片一个新列表。

于 2013-07-07T16:30:20.650 回答
0

我认为到目前为止的所有答案都缺少找到最长链的要求（至少基于您的示例输出）。

我建议的解决方案是递归解析所有可能构建的链，并返回最长的结果。该函数如下所示：

def generateTuples(list, offset, value = None):
  if value == None: value = list[offset]
  list = list[:offset]+list[offset+1:]
  res = []
  for i,(a,b) in enumerate(list):
    if value[1] in (a,b):
      if value[1] == a:  
        subres = generateTuples(list, i, (a,b))
      else:
        subres = generateTuples(list, i, (b,a))
      if len(subres) > len(res):
        res = subres
  return [value] + res

你会这样称呼它：

results = generateTuples(a, 1, (3,1))

制作清单：

[(3, 1), (1, 2), (2, 3), (3, 4), (4, 7), (7, 8), (8, 12), (12, 7), (7, 6),
 (6, 2), (2, 5), (5, 6), (6, 10), (10, 5), (5, 9), (9, 10), (10, 11),
 (11, 6), (6, 3)]

该函数的第一个参数是元组的源列表，第二个参数是要使用的第一个元素的偏移量，第三个参数是可选的，但允许您覆盖第一个元素的值。当您想以相反的顺序开始元组时，后者很有用，就像您在示例中所做的那样。

于 2013-07-07T18:08:09.423 回答
0

只是添加另一种解决此问题的方法：

import random
from collections import defaultdict

lisa = [(1, 2), (3, 4), (2, 3), (4, 0), (0, 9), (9, 1)]

current_start, current_end = lisa[random.randint(0, len(lisa) - 1)]
starts = defaultdict(list)
lisb = [(current_start, current_end)]

for start, end in lisa:
    starts[start].append(end)

while True:
    if not starts[current_end]:
        break
    current_start, current_end = current_end, starts[current_end].pop()
    lisb.append((current_start, current_end))

注意：您必须确保lisa它不为空。

于 2013-07-07T18:08:50.737 回答
0

作为生成器函数：

def chained_tuples(x):
    oldlist = x[::]
    item = random.choice(oldlist)
    oldlist.remove(item)
    yield item

    while oldlist:
        item = next(next_item for next_item in oldlist if next_item[0] == item[1])
        oldlist.remove(item)
        yield item

如前所述，如果您的列表实际上并非一直可链接，您将得到不完整的响应，例如您的示例列表。

于 2013-07-07T17:32:56.520 回答