Перестановки с дополнительными ограничениями

Question

У меня есть набор элементов, например: {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} на матрице слотов для жителей.

• https://math.stackexchange.com/questions/519056/does-a-matrix-represent-a-bijection
• https://math.stackexchange.com/questions/509563/counting-permutations-with-additional-restrictions
• https://math.stackexchange.com/questions/800977/parking-cars-and-vans-into-car-van-and-car-van-parking-spots

Answer 1

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

Что вы хотите сделать, это написать класс, который запоминает решения подзадач:

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.Это приведет к сворачиванию множества идентичных подзадач в один элемент карты и дальнейшему уменьшению уменьшения экспоненциального увеличения. </p>

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

Answer 2

Вы могли бы построить дерево. Уровень 0: Создать корневой узел. Уровень 1. Добавьте каждый элемент из первого «ограничивающего набора» в качестве дочерних элементов корня. Уровень 2. Добавьте каждый элемент из второго ограничительного набора в качестве дочерних элементов каждого из узлов уровня 1. Уровень 3. Добавьте каждый элемент из третьего ограничивающего набора в качестве дочерних элементов каждого из узлов уровня 2. ...

Тогда счетчик перестановок - это число конечных узлов конечного дерева.

Редактировать

Неясно, что подразумевается под «набором предметов» {1,1,1,2,2,3,3,3}. Если это предназначено для ограничения того, сколько раз может использоваться каждое значение («1» можно использовать 3 раза, «2» дважды и т. Д.), Тогда нам потребуется еще один шаг:

• Перед добавлением узла в дерево удалите значения, используемые в текущем пути, из набора элементов. Если значение, которое вы хотите добавить, все еще доступно (например, вы хотите добавить «1», а «1» использовалось только дважды), добавьте его в дерево.

Answer 3

Вы можете рассмотреть рекурсивное решение, которое использует пул цифр (в приведенном вами примере оно будет инициализировано как {1,1,1,2,2,3,3,3}), и решит, в индекс, заданный в качестве параметра, цифра для размещения в этом индексе (используя, конечно, введенные вами ограничения).

Если хотите, я могу предоставить псевдокод.

Answer 4

Для экономии места вы можете построить ориентированный граф вместо дерева.

• Создать корневой узел.
• Создать узел для каждого элемента в первый набор и ссылка от корня до новые узлы.
• Создать узел для каждого элемента в второй набор и ссылка с каждого первого установить элемент для каждого второго элемента набора.
• ...

Тогда число перестановок - это количество путей от корневого узла до узлов окончательного набора.