Сгладить структуру и вернуть пользователей для данной группы (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

Мне было дано это как задание, и я не знаю, как ответить. Как мне это сделать?

Ну вы начинаете проектирования алгоритма для решения этой проблемы, то реализовать этот алгоритм на языке программирования - Objective-C в вашем случае.

Так начнем с рассмотрения проблемы:

Учитывая словарь ориентированный граф, представляющий вложенные группы и их членов, выравнивать структуру и вернуть все пользователи для данной группы.

Учитывая вы получили это как задание, я полагаю, вы знаете, что словарь и ориентированный граф есть. Образцы данных также, по-видимому, используют массивы - списки элементов в квадратных скобках ([, ]).

вопрос относится к данным, представляющих ориентированный граф, образец данных происходит, чтобы представлять ориентированный ациклический граф (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, который дал данные a и имя группы возвращают все члены этой группы и ее вложенные группы.
• «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) 

Вы понимаете, почему этот алгоритм потерпит неудачу, если бы были циклы? Не продолжайте, если только не делаете!

Ну теперь у вас есть алгоритм, время писать код ...

Какая ваша работа! Мы использовали словари, массивы и наборы, они представлены в Objective-C от Cocoa NSDictionary, NSArray и NSSet вместе с NSMutableX версиями каждого.

Прочитайте документацию и укажите свой алгоритм. Если вы застряли, задайте новый вопрос, включите свой алгоритм, код, который вы написали, и проблему, которая у вас есть. Кто-то, вероятно, поможет вам.

HTH