быстрое и простое программирование с использованием векторов (массивов)
У меня есть много-много-много векторов, которые мне нужно проверить на наличие дубликатов чисел с некоторой очень простой логикой первого порядка.
Я могу использовать пересечения, но это оказывается слишком медленно. Я думал, что смогу превратить это в побитовую проблему. Полный набор целых чисел известен, и каждый вектор / массив может быть представлен как набор битов, но я могу найти только половину решения.
В настоящее время я использую циклическое и векторное пересечение, но оно оказывается слишком медленным для количества проблем, которые мне нужно проверить.
Для простого примера, приведенного ниже:
E: 1 2
F: 2 4
M: 1 3
N: 4 5
A: 5 6
Проблема, которую я пытаюсь определить, — это всегда больший формат:
(E || F) && (M || N) && A -> which is proven as possible by selecting F,M,A.
Мне нужно проверить, возможно ли вышеизложенное без дубликатов.
Есть ли способ проверки таких векторов / массивов, который работает быстрее, чем 9 миллионов циклов?
Являются ли библиотеки ограничений единственным вариантом?
В попытке уточнить:
контейнеры являются std :: vector.
Векторы содержат любое целое число.
Мне нужно было бы исследовать их проблему за проблемой, чтобы определить полный набор целых чисел.
Используя заданную условную логику для выбора целых векторов, произойдет ли дублирование?
Используемые условные операторы всегда будут только «И» и «ИЛИ». Проблема, которую я перечислил, является упрощенной версией, но это действительно все, что нужно сделать. Это просто отличается по размеру.
Вывод, который меня волнует меньше всего … это может быть логическое значение, еще один вектор потенциальных дубликатов и т. Д. Я пытаюсь найти правильный инструмент для работы, а не спасения.
В моей нынешней установке я бы решил эту проблему, проанализировав принудительные элементы, такие как A, и удалив все, с чем он пересекается … (в этом случае N … тогда я бы повторил цикл и сделал бы тот же процесс с M, который теперь вынужденный выбор и удаление E, оставив меня с F.
Решение
Если я правильно понимаю проблему, то это проблема разбиения набора, где значения из определенной «юниверса» (то есть все значения в наборах) должны быть выбраны так, чтобы одно значение было только в одном из выбранных наборов. И это является определенным условием, какие возможные комбинации наборов возможны.
Я реализовал указанную (простую) проблему в MiniZinc (система программирования ограничений очень высокого уровня, см. Мою страницу MiniZinc для получения дополнительной информации и дополнительных ссылок: http://www.hakank.org/minizinc/ ).
Модель здесь: http://www.hakank.org/minizinc/set_partition_stackoverflow.mzn
и копируется ниже полностью:
включите "globals.mzn";
int: n = 5; % количество комплектов
массив [1..n] из набора int: s =
[
{1,2},% E
{2,4},% F
{1,3},% М
{4,5},% N
{5,6}% А
];
% Все значения («вселенная»)
набор int: values = {j | я в 1..n, j в s [i]};
% переменные решения
массив [1..n] из var bool: x; % какой набор (в с) выбрать
массив [1..n] из множества значений var: xs; % выбранных наборов
решить удовлетворить;
% Минимизировать количество выбранных наборов
% решить минимизировать сумму (i в 1..n) (bool2int (card (xs [i])> 0));
ограничение
% Состояние
% (E || F) (M || N)
((x [1] \ / x [2]) / \ (x [3] \ / x [4]) / \ x [5])
/ \
Forall (я в 1..n) (
% Если этот набор выбран (в x [i]), поместите s [i] в xs [i]
(x [i] xs [i] = s [i])
/ \% убедитесь, что не выбранные наборы представлены как {} в xs
(не (x [i]) карта (xs [i]) = 0)
)
/ \% убедитесь, что значение выбрано ровно в одном наборе
partition_set ([xs [i] | i in 1..n], значения)
;
выход
[
"x:" ++ show (x) ++ "\ n" ++
"xs:" ++ show (xs) ++ "\ n"];
Существует одно решение этой проблемы:
x: [ложь, правда, правда, ложь, правда]
xs: [{}, {2, 4}, {1, 3}, {}, 5..6]
где «x» — это логический массив, если набор должен быть выбран или нет, а «xs» содержит выбранные наборы (если набор не выбран, то элемент равен {}, т.е. пуст). Разделение наборов выполняется с помощью partition_set функция, которая гарантирует, что значение находится в одном наборе и что все значения в юниверсе (набор «значения») находятся в некотором наборе.
Я не уверен, что эта модель MiniZinc поможет вообще, но вы можете рассматривать это как своего рода вдохновение, если ничего больше. Кроме того, обработка условия жестко запрограммирована в этой модели, поэтому здесь она не рассматривается.
Система CP на основе C ++ Gecode (http://www.gecode.org/) имеет поддержку для переменных набора и ограничения раздела (называемого в Gecode «дизъюнкт»), хотя я не проверял его для этой проблемы.
Вот пример того, как «дизъюнкт» можно использовать в стандартной проблеме с разделами: http://www.hakank.org/gecode/set_partition.cpp .
Другие решения
Других решений пока нет …
detector