2016-03-18 3 views
-4

ネストしたグループとそのメンバーを表す有向グラフのディクショナリを指定すると、構造がフラット化され、特定のグループのすべてのユーザーが返されます。特定のグループ(iOS)の構造をフラットにしてユーザーを返す

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'] 

私は割り当てとしてこれを与えられましたが、回答する方法はわかりません。これについてどうすればいいですか?

+0

あなたが表示できる試みはありますか?辞書とグループ名を受け取り、そのグループのメンバーと入れ子になったグループ(そしてそれらの入れ子にされたグループの入れ子になったグループなど)を含む配列を返す関数を書く必要があるようです。あなたは再帰を使用する必要はありませんが、おそらく合理的なアプローチです。また、重複を避けるための簡単な方法としてNSMutableSetを見てください。 – Paulw11

+0

私はしようとしましたが、私はどこで正直でも始めることができませんでした。 –

+0

まず、辞書と文字列を受け取り、配列を返す関数を実装します。その関数では、グループのメンバーを含む新しい配列を作成する必要があります。グループにネストされたグループがあるかどうかを確認する必要があります。もしそうなら、* group *のメンバを取得してください。これを行うには 'flattenGroup'を使うことができます。また、それらのメンバを配列に追加することもできます。 – Paulw11

答えて

2

私は割り当てとしてこれを与えられましたが、回答する方法はわかりません。これについてどうすればいいですか?あなたのケースでのObjective-C -

さて、あなたが問題を解決するためにアルゴリズムを設計することにより開始し、その後、あなたはそのアルゴリズムにプログラミング言語を実装しています。

だから、問題を見て、起動します。

ネストされたグループとそのメンバーを表す有向グラフの辞書、を考えると、構造を平らにし、特定のグループのすべてのユーザーを返します。あなたは私はあなたが辞書有向グラフが何であるかを知っていると仮定割り当てとしてこれを与えられてきたが与えられ

。サンプルデータはアレイ - 角括弧([])の項目のリストを使用するようにも見えます。

質問が有向グラフを表すデータを参照して、サンプルデータを非循環有向グラフ(DAG)を表現するために起こります。データにサイクルが存在する可能性がある場合は、アルゴリズムでそれらを処理する必要があります。アルゴリズムがまったく文字通り円のまわりを永遠に終わらせることができない場合は...実際にはDAG-サイクルはありません。

問題も含まれています:サンプルデータとサンプルクエリと一緒に

def flattenGroup(members_by_groups, group_name): 

を:

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

だから何な情報、我々は質問から持っています:

  • 「有向グラフの辞書を考える」 - あなたは有向グラフを持って、私たちは、「ネストされたグループとそのメンバーを表す」辞書
  • &サンプルデータとして表される、そのA DAGを想定しているメンバーのリスト(配列)とネストされたグループ
  • 「構造を平坦化し、特定のグループのすべてのユーザーを返す」
  • & "def flattenGroup(members_by_groups, group_name):のリスト: - 辞書内の各ノード/エントリは、それ自体は、二つのアイテムを含む辞書であります" - アルゴリズムを生成する flattenGroup aとグループ名は、そのグループとそのネストされたグループのすべてのメンバーを返します。
  • flattenGroup(MEMBERS_BY_GROUPS, 'Group2') -> ['User4', 'User5', 'User6', 'User7', 'User8', 'User9',, 'User10', 'User11'] - DAGを以下の時に、それが二回検出された、サンプルデータをチェック - クエリは例えばUser4は一度だけ発生する(無重複を含まない、リストに(配列)([ & ])を返す必要があります表示されます)、注文することができます(これはちょうど偶然かもしれません)。私たちは(擬似コードで)アルゴリズムをオフに読み取ることができることを考えると

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

関連する問題