Распознать наборы чисел в наборе наборов - PullRequest
Новая
       12

Распознать наборы чисел в наборе наборов

2 голосов
/ 21 октября 2011

У меня есть коллекция наборов с номерами в нем.Скажите 

A = {-2, 5, 6, 8}  
B = {-2, 4}  
C = {-2, 4, 6, 8}  
D = {1, -2, 15}  
E = {1, 4, 15}  
F = {1, 15}  
G = {2, 5, 6, 15}  
H = {2, 6, 15}

Теперь я хочу найти набор из 4 чисел и найти наборы, которые принадлежат этому набору.Например, я могу определить здесь набор X = {1, -2, 4, 15}, и мы видим, что B, D, E и F принадлежат этому набору.Найти эти наборы не очень сложно.

Однако проблема, с которой я сталкиваюсь, заключается в том, что я хочу идентифицировать все наборы с длиной m чисел в этой коллекции.Так что на самом деле, принимая приведенный выше пример в качестве входных данных, алгоритм получает m = 4 и {A,B,C,D,E,F,G,H} в качестве входных данных и дает мне {B,D,E,F} и {B, C} (поскольку все они содержат числа в наборе {-2, -4, 6, 8}).

Единственный способ, которым я мог придумать ответ, - это сгенерировать все возможные наборы length = 4 с числами в доступных наборах и определить, подходит ли каждый набор.Это кажется немного тупым.

Есть хорошие советы?(Java или PHP)?

Ответы [ 2 ]

1 голос
/ 21 октября 2011

В Java вы можете использовать метод коллекций retainAll() или статический метод Collections.disjoint(a,b), чтобы либо найти элементы, содержащиеся в них обоих, либо просто проверить, имеют ли они общие элементы.

Пример: 

Set<Integer> setA = new HashSet<Integer>();
setA.add( -2 );
setA.add( 5 );
setA.add( 6 );
setA.add( 8 );

Set<Integer> setB = new HashSet<Integer>();
setB.add( -2 );
setB.add( -4 );
setB.add( 6 );
setB.add( 8 );

//fill with all values from setA
HashSet<Integer> setAB = new HashSet<Integer>( setA );
//keep only those values that are contained in setB as well
setAB.retainAll( setB );


System.out.println( setAB ); //prints "[-2, 8, 6]"

System.out.println( "A and B overlap: " + !Collections.disjoint( setA, setB ) ); //prints "A and B overlap: true"

Если у вас есть набор наборов, например List<Set<Integer>>, выполните итерацию по ним и сравните каждый набор с входным набором.

В качестве альтернативы вы можете использовать класс коллекций Apache Commons CollectionUtils, которыйпредоставляет удобные методы, такие как CollectionUtils.containsAny( collection1,collection2 ) или CollectionUtils.union( collection1,collection2 ).

Google Guava также может иметь аналогичный класс.

0 голосов
/ 21 октября 2011

Я бы решил эту проблему рекурсивно.Рассмотрим один набор.Если взятие элементов из этого набора принесет число элементов больше, чем m, то рассмотрим следующий набор.Возьмите элементы из этого набора.Если больше нет наборов для рассмотрения, то у вас есть некоторый набор наборов в качестве возможного результата.Если число элементов в этом результате равно m, то взять этот результат.Теперь «рассмотрим» последний рассматриваемый набор и рассмотрим следующий набор.Повторяйте, пока не останется больше подходов для рассмотрения.В конце удалите все результаты, которые являются подмножествами существующих результатов.

...