Поиск перекрывающихся данных в массивах

Мы пишем приложение С#, которое поможет удалить ненужные ретрансляторы данных. Повторитель может быть удален только в том случае, если полученные данные all получены другими ретрансляторами. Что нам нужно в качестве первого шага, поясняется ниже:

У меня есть набор массивов int, например

а. {1, 2, 3, 4, 5}

б. {2, 4, 6, 7}

с. {1, 3, 5, 8, 11, 100}

Это могут быть тысячи таких массивов. Мне нужно найти массивы, которые можно удалить. Массив можно удалить только в том случае, если все его номера включены в другие массивы. В приведенном выше примере массив a можно удалить, поскольку его номера 2 и 4 находятся в массиве b, а числа 1, 3, 5 находятся в массиве c.

Какой лучший способ выполнить такую операцию?

Ответ 1

Это не оптимизированное решение для минимального количества оставшихся массивов.

сделать словарь изобилия для члена массивов. например:

1 => 2
2 => 2
3 => 2
4 => 2
5 => 2
6 => 1
7 => 1
...

Проверьте каждый из массивов, и если количество всех членов больше 1, удалите массив и уменьшите количество каждого номера в словаре.

Ответ 2

Получение минимального количества оставшихся массивов (в отличие от подмножества массивов, в которых больше нет массивов) - это NP-hard установить проблему покрытия. Однако даже с тысячами массивов существует хорошая вероятность, что если вы примените решение смешанной целочисленной программы к формулировке в связанной статье Википедии, оно сможет найти оптимальное решение.