展平结构并返回给定组（iOS）的用户

Question

给定一个表示嵌套组及其成员的有向图字典，展平结构并返回给定组的所有用户。你知道吗

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.

既然你已经被赋予了这个任务，我假设你知道什么是字典和有向图。示例数据似乎还使用数组——方括号中的项目列表（[，]）。你知道吗

问题涉及表示有向图的数据，样本数据恰好表示有向无环图（DAG）。如果你的数据中有循环，你就需要在你的算法中处理它们，如果你不这样做，你的算法可能会永远绕着循环走。。。现在让我们假设你真的只有一个DAG-没有周期。你知道吗

问题还包括：

def flattenGroup(members_by_groups, group_name):

以及示例数据和示例查询：

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

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

• “给定一个有向图的字典”-如果有一个有向图，我们假设它是一个DAG，表示为字典
• “表示嵌套组及其成员”&示例数据-字典中的每个节点/条目本身就是一个包含两个项的字典：成员列表（数组）和嵌套组列表
• “展平结构并返回给定组的所有用户”&；“def flattenGroup(members_by_groups, group_name):”-生成一个算法flattenGroup，该算法给定数据，组名返回该组及其嵌套组中的所有成员。你知道吗
• “flattenGroup(MEMBERS_BY_GROUPS, 'Group2') -> ['User4', 'User5', 'User6', 'User7', 'User8', 'User9',, 'User10', 'User11']”-看起来查询应该返回一个列表（数组）（[&；]），不包含重复项（例如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以及它们的NSMutableX版本在Objective-C中提供的。你知道吗

阅读文档并编写算法。如果你陷入困境，问一个新问题，包括你的算法，你写的代码，和你的问题。也许有人会帮你。你知道吗

HTH公司