Перестановки с дополнительными ограничениями
У меня есть ряд объектов, например: {1,1,1,2,2,3,3,3}, и набор ограничения наборов, например {{3}, {1,2}, {1,2,3}, {1,2,3}, {1,2,3}, {1,2,3}, {2,3}, {2,3}. Я ищу перестановки объектов, но первый элемент должен быть 3, и второе должно быть 1 или 2 и т.д.
Одна такая перестановка, которая соответствия: {3,1,1,1,2,2,3}
Существует ли алгоритм для подсчета всех перестановок для этой проблемы в целом? Существует ли название этого типа проблемы?
Для иллюстрации я знаю, как решить эту проблему для определенных типов "ограничения наборов". Набор объектов: {1,1,2,2,3}, Ограничения {{1,2}, {1,2,3}, {1,2,3}, {1,2}, {1,2}}. Это равно 2! / (2-1)!/1! * 4!/2!/2!. Эффективно переставляя первые 3, так как это является самым строгим и затем переставляет остающиеся объекты, где существует комната.
Также... полиномиальное время. Это возможно?
ОБНОВЛЕНИЕ: Это обсуждено далее в ссылках ниже. Проблему выше называют, "считая идеальные соответствия", и каждое ограничение перестановки выше представлено {0,1} на матрице слотов жителям.
4 ответа
Все остальные решения здесь являются экспоненциальными по времени - даже для случаев, в которых они не должны быть. Эта проблема имеет аналогичную подструктуру, поэтому ее следует решать с помощью динамического программирования.
Что вы хотите сделать, так это написать класс, который запоминает решения подзадач:
class Counter {
struct Problem {
unordered_multiset<int> s;
vector<unordered_set<int>> v;
};
int Count(Problem const& p) {
if (m.v.size() == 0)
return 1;
if (m.find(p) != m.end())
return m[p];
// otherwise, attack the problem choosing either choosing an index 'i' (notes below)
// or a number 'n'. This code only illustrates choosing an index 'i'.
Problem smaller_p = p;
smaller_p.v.erase(v.begin() + i);
int retval = 0;
for (auto it = p.s.begin(); it != p.s.end(); ++it) {
if (smaller_p.s.find(*it) == smaller_p.s.end())
continue;
smaller_p.s.erase(*it);
retval += Count(smaller_p);
smaller_p.s.insert(*it);
}
m[p] = retval;
return retval;
}
unordered_map<Problem, int> m;
};
Код иллюстрирует выбор индекса i, который следует выбирать в том месте, где есть v [i] .size () маленький. Другой вариант - выбрать число n, которое должно быть таким, для которого есть несколько мест v, в которые оно может быть помещено. Я бы сказал, что минимум из двух решающих факторов должен победить.
Кроме того, вам нужно будет определить хеш-функцию для задачи - это не должно быть слишком сложно с использованием хеш-хешей Boost.
Это решение можно улучшить, заменив вектор на набор <> и определив оператор <для unordered_set. Это сведет множество идентичных подзадач в один элемент карты и еще больше уменьшит экспоненциальный взрыв.
Это решение может быть дополнительно улучшено путем создания одинаковых экземпляров Задачи, за исключением того, что числа переупорядочиваются в хэш-значениях на одно и то же значение и сравниваются, чтобы быть одинаковыми.
Вы можете рассмотреть рекурсивное решение, которое использует пул цифр (в приведенном вами примере он будет инициализирован как {1,1,1,2 , 2,3,3,3}) и решает по индексу, указанному в качестве параметра, какую цифру разместить в этом индексе (конечно, используя указанные вами ограничения).
Если хотите, я могу предоставить псевдокод.
Чтобы сэкономить место, вы можете построить ориентированный граф вместо дерева.
- Создайте корневой узел.
- Создайте узел для каждого элемента в первом наборе и свяжите корень с новыми узлами.
- Создайте узел для каждого элемента во втором наборе и свяжите каждый первый элемент набора с каждым вторым элементом набора.
- ...
Количество перестановок - это количество путей от корневого узла к узлам окончательного набора.
Вы можете построить дерево. Уровень 0: Создать корневой узел. Уровень 1: Добавьте каждый элемент из первого "ограничивающего множества" в качестве дочерних элементов корня. Уровень 2: Добавьте каждый элемент из второго ограничивающего множества в качестве дочерних элементов каждого из узлов уровня 1. Уровень 3: добавьте каждый элемент из третьего ограничивающего множества в качестве дочерних элементов каждого из узлов уровня 2. ...
Число перестановок - это количество листовых узлов конечного дерева.
Редактировать
Неясно, что подразумевается под "множеством элементов" {1,1,1,2,2,3,3,3}. Если это означает ограничение на то, сколько раз каждое значение может быть использовано ("1" может быть использовано 3 раза, "2" дважды и т.д.), тогда нам нужен еще один шаг:
- Перед добавлением узла в дерево, удалите значения, использованные на текущем пути, из набора элементов. Если значение, которое вы хотите добавить, все еще доступно (например, вы хотите добавить "1", а "1" до сих пор использовалось только дважды), то добавьте его в дерево.