Поиск самого большого подмножества элементов, который не коррелирует

Question

У меня есть набор целых чисел, и я хочу найти самое большое подмножество, в котором элементы не коррелируют друг с другом определенным образом. Например, подмножество, в котором, если какой-либо из элементов умножается на 13, результат не находится в подмножестве.

Моя первая мысль - перебрать все возможные подмножества, отфильтровать их, которые не соответствуют этому условию, а затем найти самый большой, но это слишком медленно, и я не знаю, как сгенерировать все возможные подмножества ,

Answer 1

Я буду отвечать на этот вопрос (из комментариев). В общем, нет никакого хорошего решения для любой «корреляции»

Отношения следующие: если вы несколько элементов из подмножества на некоторое число, то итоговое число не должно быть в подмножестве.

Если ваш номер m

Вы можете создать все сети x, x*m, x*m*m, ...., так что все количество в цепи в наборе, x/m не является

Remove каждый второй элемент, т.е. x*m^2, x*m^4 из оригинального комплекта. Элементы слева - ваш целевой набор.

Answer 2

Лучше всего построить граф и найти вершины с большинством ребер и удалить их, пока вы не избавитесь от всех ребер. Сложность - O (N^2).

Вот подробный алгоритм:

for each possible pair (x, y) from the source set 
begin 
    if x = y * 13 or y = x * 13 then make edge between x and y 
end 
while graph has edges 
begin 
    let V = find: a vertex with maximum count of edges (it can be 1 or 2) 
    remove V from the graph 
end 
result: the remaining vertexes in the graph