2016-08-13 5 views
5

私はセットの交差点で労働組合にセットのコレクションを必要とし、ここでは、そのような署名で交差点の集合をフィルタリングする方法は?

Collection<Set<Integer>> filter(Collection<Set<Integer>> collection); 

を関数を記述は、この例では、そのセットを見ることができますセット

1) {1,2,3} 
2) {4} 
3) {1,5} 
4) {4,7} 
5) {3,5} 

の簡単な例であります1,3、および5が交差する。それを新しいセット{1,2,3,5}として書き直すことができます。また、交差を持つ2つのセットもあります。それらは24であり、新しいセット{4,7}を作成できます。出力結果は、{1,2,3,5}{4,7}の2つのセットのコレクションになります。

このタスクのどの時点から解決するのか分かりません。

+0

あなたは最終的な出力がどうあるべきか、より具体的なことはできますか?パワーセット? – ketrox

+0

確かに。これは2つの集合( '{1,2,3,5}'と '{4,7}')の集合でなければなりません。 – Mark

+0

@ketrox任意のセットの威力はランダムになる可能性があります。 – Mark

答えて

0

これはあなたのユースケースを解決するはずです。それは、より効率的な方法で実現することができるが、私は、これはあなたに開始するためのアイデアを与える必要がありますね:

private static Collection<Set<Integer>> mergeIntersections(Collection<Set<Integer>> collection) { 
    Collection<Set<Integer>> processedCollection = mergeIntersectionsInternal(collection); 
    while (!isMergedSuccessfully(processedCollection)) { 
     processedCollection = mergeIntersectionsInternal(processedCollection); 
    } 
    return processedCollection; 
} 

private static boolean isMergedSuccessfully(Collection<Set<Integer>> processedCollection) { 
    if (processedCollection.size() <= 1) { 
     return true; 
    } 
    final Set<Integer> mergedNumbers = new HashSet<>(); 
    int totalNumbers = 0; 
    for (Set<Integer> set : processedCollection) { 
     totalNumbers += set.size(); 
     mergedNumbers.addAll(set); 
    } 
    if (totalNumbers > mergedNumbers.size()) { 
     return false; 
    } 
    return true; 
} 

private static Collection<Set<Integer>> mergeIntersectionsInternal(Collection<Set<Integer>> collection) { 
    final Collection<Set<Integer>> processedCollection = new ArrayList<>(); 
    // ITERATE OVER ALL SETS 
    for (final Set<Integer> numberSet : collection) { 
     for (final Integer number : numberSet) { 
      boolean matched = false; 
      // ITERATE OVER ALL PROCESSED SETS COLLECTION 
      for (final Set<Integer> processedSet : processedCollection) { 
       // CHECK OF THERE IS A MATCH 
       if (processedSet.contains(number)) { 
        matched = true; 
        // MATCH FOUND, MERGE THE SETS 
        processedSet.addAll(numberSet); 
        // BREAK OUT OF PROCESSED COLLECTION LOOP 
        break; 
       } 
      } 
      // IF NOT MATCHED THEN ADD AS A COLLECTION ITEM 
      if (!matched) { 
       processedCollection.add(new HashSet<>(numberSet)); 
      } 
     } 
    } 
    return processedCollection; 
} 

これは、それを実行する方法である:ここでは

public static void main(String[] args) { 
     final Collection<Set<Integer>> collection = new ArrayList<>(); 
     final Set<Integer> set1 = new HashSet<>(); 
     set1.add(1); 
     set1.add(2); 
     set1.add(3); 
     collection.add(set1); 

     final Set<Integer> set2 = new HashSet<>(); 
     set2.add(4); 
     collection.add(set2); 

     final Set<Integer> set3 = new HashSet<>(); 
     set3.add(1); 
     set3.add(5); 
     collection.add(set3); 

     final Set<Integer> set4 = new HashSet<>(); 
     set4.add(4); 
     set4.add(7); 
     collection.add(set4); 

     final Set<Integer> set5 = new HashSet<>(); 
     set5.add(3); 
     set5.add(5); 
     collection.add(set5); 

     System.out.println(mergeIntersections(collection)); 

    } 
+0

私はこれが必要に応じて動作するのではないかと疑います。集合AがBとCと交差する場合、AuBuC *と* BuCの両方が出力リストに入らないような仕組みはありません。また、これはO(大規模な)ランタイムのように見えます。 –

+0

はい、出力は3つのセット( '{1,2,3,5}'、 '{5,2}'、 '{4}')の集合になります。 – Mark

+0

@マーク。私はあなたが言及した例の設定値に対してそれをテストし、うまくいきました。 –

-1

は私の行くのです。すべてのセットを入力コレクションから削除しますが、これは最初にコピーを作成することで簡単に修正できます。入力コレクションの各セットは変更されません。私の実装では、Ajayの主な方法は[[1, 2, 3, 5], [4, 7]]です。この問題を解決するための

Collection<Set<Integer>> filter(Collection<Set<Integer>> collection) { 
    Collection<Set<Integer>> mergedSets = new ArrayList<>(collection.size()); 
    // for each set at a time, merge it with all sets that intersect it 
    while (! collection.isEmpty()) { 
     // take out the first set; make a copy as not to mutate original sets 
     Set<Integer> currentSet = new HashSet<>(removeOneElement(collection)); 
     // find all intersecting sets and merge them into currentSet 
     // the trick is to continue merging until we find no intersecting 
     boolean mergedAny; 
     do { 
      mergedAny = false; 
      Iterator<Set<Integer>> it = collection.iterator(); 
      while (it.hasNext()) { 
       Set<Integer> candidate = it.next(); 
       if (intersect(currentSet, candidate)) { 
        it.remove(); 
        currentSet.addAll(candidate); 
        mergedAny = true; 
       } 
      } 
     } while (mergedAny); 
     mergedSets.add(currentSet); 
    } 
    return mergedSets; 
} 

private static Set<Integer> removeOneElement(Collection<Set<Integer>> collection) { 
    Iterator<Set<Integer>> it = collection.iterator(); 
    Set<Integer> element = it.next(); 
    it.remove(); 
    return element; 
} 

/** @return true if the sets have at least one element in common */ 
private static boolean intersect(Set<Integer> leftSet, Set<Integer> rightSet) { 
    // don’t mutate, take a copy 
    Set<Integer> copy = new HashSet<>(leftSet); 
    copy.retainAll(rightSet); 
    return ! copy.isEmpty(); 
} 
+0

なぜdownvote?ちょっと興味があるんだけど。 –

+0

パフォーマンスが重要でメンバーがあまりにも多すぎない範囲(たとえば1〜100、おそらく1〜1000)であれば、より効率的な実装を開発するためにjava.util.BitSetを調べることをお勧めします。 –

0

エレガントな方法は、あなたが同じセットからの少なくとも一つの他の要素で設定した入力から要素を接続し、接続された部品に見て無向グラフを、使用しています。

enter image description here

から、我々は容易に接続コンポーネントを推論することができる:

だからあなたの例のグラフ表現は{1、2、3、5}および{4,7}。ここで

は私のコードです:

Collection<Set<Integer>> filter(Collection<Set<Integer>> collection) { 

    // Build the Undirected Graph represented as an adjacency list 
    Map<Integer, Set<Integer>> adjacents = new HashMap<>(); 
    for (Set<Integer> integerSet : collection) { 
     if (!integerSet.isEmpty()) { 
      Iterator<Integer> it = integerSet.iterator(); 
      int node1 = it.next(); 
      while (it.hasNext()) { 
       int node2 = it.next(); 

       if (!adjacents.containsKey(node1)) { 
        adjacents.put(node1, new HashSet<>()); 
       } 
       if (!adjacents.containsKey(node2)) { 
        adjacents.put(node2, new HashSet<>()); 
       } 
       adjacents.get(node1).add(node2); 
       adjacents.get(node2).add(node1); 
      } 
     } 
    } 

    // Run DFS on each node to collect the Connected Components 
    Collection<Set<Integer>> result = new ArrayList<>(); 
    Set<Integer> visited = new HashSet<>(); 
    for (int start : adjacents.keySet()) { 
     if (!visited.contains(start)) { 
      Set<Integer> resultSet = new HashSet<>(); 
      Deque<Integer> stack = new ArrayDeque<>(); 
      stack.push(start); 
      while (!stack.isEmpty()) { 
       int node1 = stack.pop(); 
       visited.add(node1); 
       resultSet.add(node1); 
       for (int node2 : adjacents.get(node1)) { 
        if (!visited.contains(node2)) { 
         stack.push(node2); 
        } 
       } 
      } 
      result.add(resultSet); 
     } 
    } 

    return result; 
} 
+1

私は誰もがこの特定の質問に完全な口頭の解決策をなぜ提供しているのか分かりません。これはあまりスタックオーバーフローではありません。 –

+1

@OliverCharlesworthそれは面白いから –

0

最善の解決策はUnion-Find algorithm

implemtationです私見:

public class UnionFind { 

    Set<Integer> all = new HashSet<>(); 
    Set<Integer> representants = new HashSet<>(); 
    Map<Integer, Integer> parents = new HashMap<>(); 

    public void union(int p0, int p1) { 
     int cp0 = find(p0); 
     int cp1 = find(p1); 
     if (cp0 != cp1) { 
      int size0 = parents.get(cp0); 
      int size1 = parents.get(cp1); 
      if (size1 < size0) { 
       int swap = cp0; 
       cp0 = cp1; 
       cp1 = swap; 
      } 
      parents.put(cp0, size0 + size1); 
      parents.put(cp1, cp0); 
      representants.remove(cp1); 
     } 
    } 

    public int find(int p) { 
     Integer result = parents.get(p); 
     if (result == null) { 
      all.add(p); 
      parents.put(p, -1); 
      representants.add(p); 
      result = p; 
     } else if (result < 0) { 
      result = p; 
     } else { 
      result = find(result); 
      parents.put(p, result); 
     } 
     return result; 
    } 

    public Collection<Set<Integer>> getGroups() { 
     Map<Integer, Set<Integer>> result = new HashMap<>(); 
     for (Integer representant : representants) { 
      result.put(representant, new HashSet<>(-parents.get(representant))); 
     } 
     for (Integer value : all) { 
      result.get(find(value)).add(value); 
     } 
     return result.values(); 
    } 

    public static Collection<Set<Integer>> filter(Collection<Set<Integer>> collection) { 
     UnionFind groups = new UnionFind(); 
     for (Set<Integer> set : collection) { 
      if (!set.isEmpty()) { 
       Iterator<Integer> it = set.iterator(); 
       int first = groups.find(it.next()); 
       while (it.hasNext()) { 
        groups.union(first, it.next()); 
       } 
      } 
     } 
     return groups.getGroups(); 
    } 
}