2016-08-13 25 views
5

muszę unii zbiór zestawów przez przecięcie zbiorów i napisać funkcję z takim podpisemJak filtrować zbiór zestawów według przecięcia?

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

Oto prosty przykład zestawów

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

W tym przykładzie widzimy, że zestawy 1, 3 i 5 i 5 przecinają się. Możemy przepisać go jako nowy zestaw {1,2,3,5}. Mamy również dwa zestawy, które również mają skrzyżowania. Są to 2 i 4 i możemy utworzyć nowy zestaw {4,7}. Wynik wyjściowy będzie zbiorem dwóch zestawów: {1,2,3,5} i {4,7}.

Nie wiem, od którego momentu rozpocząć rozwiązywanie tego zadania.

+0

Czy można być bardziej szczegółowe, co ostateczne wyjście powinno być? Zestaw mocy? – ketrox

+0

Pewnie. Powinien to być zbiór dwóch zestawów ('{1,2,3,5}' i '{4,7}'). – Mark

+0

@ketrox moc dowolnego zestawu może być losowa. – Mark

Odpowiedz

0

To powinno rozwiązać twój przypadek użycia. Może to być realizowane w sposób bardziej efektywny, ale myślę, że to powinno dać ci pomysł na początek:

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; 
} 

Jak to wykonywane go:

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

Wątpię, aby to działało zgodnie z wymaganiami. Jeśli zestaw A przecina się z B i C, nie widzę żadnego mechanizmu, który uniemożliwiłby zarówno AuBuC *, jak i * BuC na liście wyników. Wygląda to również na środowisko wykonawcze O (coś dużego). –

+0

Tak, dane wyjściowe będą kolekcją trzech zestawów ('{1,2,3,5}', '{5,2}', '{4}'). – Mark

+0

@ Mark. Przetestowałem to na podstawie przykładowych wartości ustawionych przez ciebie i wszystko działało dobrze. –

-1

Oto mój iść. Usuwa wszystkie zestawy z kolekcji wejściowej, można to łatwo naprawić, najpierw wykonując kopię. Nie modyfikuje każdego zestawu w zbiorze wejściowym. Dzięki mojej implementacji główna metoda Ajay'a drukuje [[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

Dlaczego upadek? Po prostu ciekawy. –

+0

Jeśli wydajność jest ważna, a członkowie mają niezbyt szeroki zakres (na przykład od 1 do 100 lub od 1 do 1000), należy zapoznać się z plikiem java.util.BitSet, aby uzyskać bardziej wydajną implementację. –

0

elegancki sposób na rozwiązanie tego problemu jest użycie undirected wykresy, gdzie można połączyć element z wejściem zestaw z co najmniej jednego innego pierwiastka z tego samego zestawu, a następnie szukać podłączonych urządzeń.

Więc reprezentacja wykres swoim przykładzie:

enter image description here

i od tego możemy łatwo wywnioskować podłączonych urządzeń: {1, 2, 3, 5} i {4, 7}.

Oto mój kod:

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

Nie wiem, dlaczego wszyscy dostarczają pełnych dosłownych rozwiązań tego konkretnego pytania. To nie jest zbyt duże przepełnienie stosu. –

+1

@OliverCharlesworth Ponieważ to zabawne –

0

IMHO najlepszym rozwiązaniem jest 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(); 
    } 
} 
Powiązane problemy