展平结构和给定组的 return 用户 (iOS)

Question

给定一个有向图的字典，表示嵌套组及其成员，展平结构和return给定组的所有用户。

MEMBERS_BY_GROUPS = {
    'Group0': {
        'NestedGroups': ['Group3'],
        'Members': ['User0', 'User1']
    },
    'Group1': {
        'NestedGroups': ['Group3'],
        'Members': ['User2', 'User3', 'User4']
    },
    'Group2': {
        'NestedGroups': ['Group3', 'Group5'],
        'Members': ['User4', 'User5']
    },
    'Group3': {
        'NestedGroups': ['Group4'],
        'Members': ['User6', 'User7']
    },
    'Group4': {
        'NestedGroups': [],
        'Members': ['User8', 'User9']
    },
    'Group5': {
        'NestedGroups': [],
        'Members': ['User10', 'User11']
    }
}


def flattenGroup(members_by_groups, group_name): // (MEMBERS_BY_GROUPS, 'Group2') -> ['User4', 'User5', 'User6', 'User7', 'User8', 'User9',, 'User10', 'User11']

这是我的作业，我不知道如何回答。我该怎么做？

Answer 1

I was given this as an assignment and I do not know how to answer. How do I go about this?

好吧，你首先设计一个算法来解决问题，然后你用编程语言实现该算法 - Objective-C 在你的例子中。

所以从看问题开始：

Given a dictionary of a directed graph, representing nested groups and their members, flatten the structure and return all the users for a given group.

鉴于您已将此作为作业分配，我假设您知道什么是字典和 有向图 。示例数据似乎也使用 arrays - 方括号中的项目列表 ([, ]).

题中数据表示有向图，样本数据恰好表示有向无环图（DAG）。如果您的数据中可能存在循环，您将需要在您的算法中处理它们，如果您不这样做，您的算法可能最终会永远绕圈......目前让我们假设您实际上只有一个 DAG -没有循环。

问题还包括：

def flattenGroup(members_by_groups, group_name):

连同示例数据和示例查询：

flattenGroup(MEMBERS_BY_GROUPS, 'Group2') -> ['User4', 'User5', 'User6', 'User7', 'User8', 'User9',, 'User10', 'User11']

那么我们从问题中得到了什么信息：

"Given a dictionary of a directed graph" - 你有一个有向图，我们假设它是一个 DAG，表示为字典
"representing nested groups and their members" & 示例数据 - 字典中的每个 node/entry 本身就是一个包含两项的字典：成员列表（数组）和嵌套组列表
"flatten the structure and return all the users for a given group" & "def flattenGroup(members_by_groups, group_name):" - 生成算法 flattenGroup 给定数据和组名 return是该组及其嵌套组中的所有成员。
"flattenGroup(MEMBERS_BY_GROUPS, 'Group2') -> ['User4', 'User5', 'User6', 'User7', 'User8', 'User9',, 'User10', 'User11']" - 看来查询应该 return 一个列表（数组）（[ & ]), 不包含重复项（例如 User4 只出现一次 - 检查示例数据，在跟随 DAG 时发现两次），并被订购（这可能只是巧合）；

假设我们可以读出一个算法（伪代码）：

def flattenGroup(members_by_groups, group_name):
    { members of group_name } // the set of all members of group_name
    ∪ // union
    { members of first nested group } // the set of all members of the first nested group
    ∪ // union
    ...
    ∪ // union
    { members of last nested group }

注意：我已经写了使用集合，这既是因为以这种方式描述算法是有意义的，也是因为集合不包含重复项。使用集合还是列表来实现它是一个实现细节。

算法对您有意义吗？ 在完成之前不要继续。

现在让我们详细说明算法。第一个子表达式是：

{ members of group_name } // the set of all members of group_name

这很简单，每个节点都包含一个成员列表，无需详细说明。第二个和后续子表达式的形式为：

{ members of first nested group } // the set of all members of the first nested group

这当然更复杂，因为嵌套组的成员依次包含它的嵌套组，所以这可以详细说明，但是要做什么呢？这个子表达式的任务与我们正在编写的算法完全相同，除了不同的组，所以那一行只是：

flattenGroup(members_by_groups, first nested group)

现在整个算法是：

def flattenGroup(members_by_groups, group_name):
    { members of group_name }
    ∪
    flattenGroup(members_by_groups, first nested group)
    ∪
    ...
    ∪
    flattenGroup(members_by_groups, last nested group)

你明白为什么这个算法在有环的情况下会失败吗？ 除非你这样做，否则不要继续！

现在你有了一个算法，是时候写一些代码了...

你的工作是什么！我们使用了字典、数组和集合，这些由 Cocoa 的 NSDictionary、NSArray 和 NSSet 以及 [=28] 在 Objective-C 中提供=] 每个版本。

去阅读文档并编写你的算法。如果您遇到困难，请提出一个新问题，包括您的算法、您编写的代码以及您遇到的问题。有人可能会帮助你。

HTH

展平结构和给定组的 return 用户 (iOS)

Flatten structure and return users for given group (iOS)

python

cocoa

pyobjc