代码之家 › 专栏 › 技术社区 › anonymous coward

如何从层次结构创建嵌套列表

data-structures django python

0

anonymous coward · 技术社区 · 7 年前

我有一些用户邀请,其中一个邀请 from 和 to 用户属性。

例如。,

UserInvite1.from = User1
UserInvite1.to = User2

UserInvite1b.from = User1
UserInvite1b.to = User4

UserInvite2.from = User2
UserInvite2.to = User3

UserInvite3.from = User2
UserInvite3.to = User5

因此,user1邀请了user2和user4;user2邀请了user3和user5。

给出这些邀请的列表,例如, [UserInvite1, UserInvite2, ... ] , 或者其他迭代它们的方法 (?)我如何生成一个代表被邀请的“分层”(嵌套)列表?

例如,从“根”user1开始,我想要一个嵌套列表,如下所示:

>>> make_nest_list_from_invites([invites])
[User1, [User2, [User3, User5], User4]]

如果你熟悉Django,我试着从我的“邀请”到一些层次化的东西,我可以把它输入到Django模板标签中。 unordered_list

很明显这有点像穿越树,但我现在很困惑。我尝试了一些递归的东西,但是在一个扔东西的地方保持了一个额外的嵌套。

更新:我尝试过的东西的例子

def tree_from_here(user):
    children = get_children(user)
    if children:
        return [user, [tree_from_here(c) for c in children]]
    else:
        return user

它给出:

>>> tree_from_here(User1)
[<User: 1>, [[<User: 2>, [<User: 3>, <User: 5>]], <User: 4>]]

这对我现在的用户来说几乎是正确的, 除了嵌套在第二个元素中太深。

我在尝试:

[<User: 1>, [<User: 2>, [<User: 3>, <User: 5>], <User: 4>]]

我觉得它在盯着我的脸,但我不知道如何在此刻归还正确的东西。

1 回复 | 直到 7 年前

1

wiesion 7 年前

我很难理解你对嵌套结构的这种重新构造的想法,但是经过大量思考和编写代码,我相信我理解了,所以我猜这就是你想要的-代码和在线演示中的描述: https://repl.it/repls/EarlyWeeklyThings -是一个很好的挑战,谢谢

from pprint import pprint

# dummy user class
class User(object):
  def __init__(self, user_id):
    self.user_id = user_id
  def __repr__(self):
    return "User{}".format(self.user_id)

# dummy invite class 
class UserInvite(object):
  def __init__(self, from_user, to_user):
    self.from_user = from_user
    self.to_user = to_user
  def __repr__(self):
    return "From {} to {}".format(self.from_user, self.to_user)

# create 10 dummy users to create invites
users = [User(user_id) for user_id in range(1,11)]

# use natural numbers to reflect invites
# adjust in list comprehension
invite_map = (
  (1, 3), (1, 5), 
  (2, 4), (2, 6),
  (3, 7), (3, 8),
  (4, 9),
  (9, 10)
)

# create invitations based on the invite_map, fix natural numbers
example_invites = [
  UserInvite(users[inviter-1], users[invitee-1]) for inviter, invitee in invite_map
]

pprint(example_invites)
# =>
# [From User1 to User3,
#  From User1 to User5,
#  From User2 to User4,
#  From User2 to User6,
#  From User3 to User7,
#  From User3 to User8,
#  From User4 to User9,
#  From User9 to User10]

def get_nested_invites(invites, invited_by=None):
  result = []
  if not invited_by:
    # Assume that initial inviters were not invited by anyone
    # Use set comprehensions to avoid duplicates and for performance
    invitees = {invite.to_user for invite in invites}
    inviters = {invite.from_user for invite in invites if invite.from_user not in invitees}
  else:
    # Get the next potential inviters given their inviter
    # Use set comprehension to avoid duplicates and for performance
    inviters = {invite.to_user for invite in invites if invite.from_user == invited_by}
  for inviter in inviters:
    # Add the invited user/potential inviter 
    result.append(inviter)
    # Let's get nesty
    invitees = get_nested_invites(invites, inviter)
    if invitees:
      result.append(invitees)
  return result

pprint(get_nested_invites(example_invites))
# =>
# [User1,
#  [User3, [User7, User8], User5],
#  User2,
#  [User6, User4, [User9, [User10]]]]

pprint(get_nested_invites(example_invites, users[1]))
# =>
# [User6, User4, [User9, [User10]]]