python - 使用生成家谱的元组列表拆分元组
问题描述
让我们使用元组和列表来表示家谱。每个人都表示为一个元组。元组的第一个元素是这个人的名字。元组的第二个元素是一个包含这个人的孩子的列表。每个孩子都表示为一个元组本身。如果一个人没有孩子,他/她的孩子列表是空的。例如,如果 Mary 没有孩子,则表示为 ('Mary', [])。如果 Jane 有两个名为 Nick 和 Wendy 的孩子,而 Nick 和 Wendy 都没有孩子,则 Jane 表示为 ('Jane', [('Nick', []), ('Wendy', [])])。如果 Mary 和 Jane 是 Frank 的孩子,而 Frank 没有其他孩子,则 Frank 表示为 ('Frank', [('Mary', []), ('Jane', [('Nick', [ ]), ('温迪', [])])])。
定义一个名为 head 的函数,该函数get_family_members()
接受一个名为 head 的人的表示,他表示一个家谱的头部。头部可能有几个孩子、孙子、曾孙等。该函数以列表的形式返回此人家庭的所有成员(包括他/她自己)。成员应按代排序。换句话说,第 n 代的人应该总是出现在第 (n-1) 代的人之后。此外,同一代人应根据他们在原始列表中的顺序进行排序。例如,如果 Nick 和 Wendy 属于同一代,并且 Nick 在原始列表中出现在 Wendy 之前,那么 Nick 在返回列表中应该出现在 Wendy 之前。
这是我所做的:
def get_family_members(head):
# modify the code below
new_dict = {}
return_list = []
new_list = head
#append first ele in
return_list.append(new_list[0])
new_dict[new_list[0]] = new_list[1]
# new_list = new_list[1]
key = new_list[0]
print(new_dict[key])
end = False
j = 0
if new_dict[key] != []:
while end == False:
i = 0
for tuple1 in new_dict[key]:
if tuple1[i] not in return_list:
return_list.append(tuple1[i])
new_dict[tuple1[i]] = tuple1[i+1]
print("element",tuple1[i])
print("new list",new_dict[tuple1[i]])
print("return list",return_list)
if tuple1[i+1] != []:
key = tuple1[i]
else:
end = True
return return_list
print("key",key)
return [key]
但是当我使用这个测试用例时它似乎是错误的:
print("Test Case #1:")
print()
family_head = ('Mary', [])
result_list = get_family_members(family_head)
print("Expected: ['Mary']")
print("Actual : " + str(result_list))
print()
print("Expected type of returned value: <class 'list'>")
print("Actual type of returned value : " + str(type(result_list)))
print()
print("====================")
print()
# Test Case 2:
print("Test Case #2:")
print()
family_head = ('Jane', [('Nick', []), ('Wendy', [])])
result_list = get_family_members(family_head)
print("Expected: ['Jane', 'Nick', 'Wendy']")
print("Actual : " + str(result_list))
print()
print("====================")
print()
# Test Case 3:
print("Test Case #3:")
print()
family_head = ('Frank', [('Mary', []), ('Jane', [('Nick', [])])])
result_list = get_family_members(family_head)
print("Expected: ['Frank', 'Mary', 'Jane', 'Nick']")
print("Actual : " + str(result_list))
print()
print("====================")
print()
# Test Case 4:
print("Test Case #4:")
print()
family_head = ('Alan', [('Bob', [('Chris', [])]), ('Eric', [])])
result_list = get_family_members(family_head)
print("Expected: ['Alan', 'Bob', 'Eric', 'Chris']")
print("Actual : " + str(result_list))
print()
print("====================")
print()
# Test Case 5:
print("Test Case #5:")
print()
family_head = ('Alan', [('Bob', [('Chris', []), ('Debbie', [('Cindy', [])])]), ('Eric', [('Dan', []), ('Fanny', [('George', [])])]), ('Hannah', [])])
result_list = get_family_members(family_head)
print("Expected: ['Alan', 'Bob', 'Eric', 'Hannah', 'Chris', 'Debbie', 'Dan', 'Fanny', 'Cindy', 'George']")
print("Actual : " + str(result_list))
print()
print("====================")
print()
解决方案
考虑以下树
Root
1 2 3 4
11 12 13 21 22 41 42
可以写成
(Root,[
(1,[(11,[]),12,13]), (2,[21,22]), (3,[]), (4,[41,42])
])
输出应该是
[Root, 1 ,2, 3, 4, 11, 12, 13, 21, 22]
(请注意,对于所有叶子(但 11)我没有写一个(12,[])
元组,而是直接写原始类型12
现在这种遍历称为bfs。
由于我们有一棵没有循环的树,因此可以进一步简化 bfs。
- 仍然保留将当前“孩子”的探索延迟到堆栈后面的想法
- 关于元组“11”的东西,
stack += children
没有修改if children==[]
所以这仍然可以
def get_family_members(family):
(root, children) = family
L = [root]
stack = children
while len(stack):
node = stack.pop(0)
#if we pushed a leaf
if type(node) is not tuple:
L += [node]
else:
#add children to the __back__ of the stack
(child, children) = node
L += [child]
stack += children
return L
fam = (0,[
(1,[(11,[]),12,13]), (2,[21,22]), (3,[]), (4,[])
])
print(get_family_members(fam))
#[0, 1, 2, 3, 4, 11, 12, 13, 21, 22]
推荐阅读
- sql - 如何从客户端函数 \crosstabview 的结果创建表
- regex - 使用正则表达式验证 kubernetes 版本
- node.js - 获取不使用 id 的 Firestore 子集合
- android - java.lang.NoSuchMethodError: okhttp3.internal.Internal.initializeInstanceForTests 在 Android Studio 4.1
- python - Python 返回列表的总和,其中 5 计为双倍,5 之后的数字计为四倍
- amazon-web-services - 如何将 Snowflake 作为应用程序后端数据库进行快速搜索
- python - 如何将一列中基于不同类别的数据行提取到单独的文本文件中?
- python - 在迁移学习 ValueError 中:无法将 NumPy 数组转换为张量
- scalardb - 如何使用 Cassy 备份工具恢复到不同的环境?
- javascript - 如何从 fetch 返回数据并将数据用于另一个函数