Это, безусловно, тот случай, когда исходная задача изоморфна задаче подсчета r -комбинаций мультимножества размера 2 r .
В качестве альтернативы формуле включения-исключения (которая, безусловно, имеет аналитическое значение, но, возможно, имеет меньшее алгоритмическое значение), мы можем построить рекурсивное решение, которое вычисляет число k -комбинаций установить для всех значений k , используя очень похожий подход к рекурсии, применяемый в рекурсивном алгоритме для подсчета биномиальных коэффициентов C ( n , k ), количество k -комбинаций из набора n элементов.
Предположим, мы представляем мультимножество в виде отсортированного вектора V размера n (где n & равно; 2 r ). (Технически, его не нужно сортировать; достаточно, чтобы он был «сгруппирован», чтобы все идентичные элементы были последовательными. Однако самый простой способ сделать это - отсортировать вектор.) Мы хотим получить все уникальные k -комбинации этого вектора. Все такие комбинации имеют одну из двух форм:
«Выберите первый элемент». Комбинация начинается с V 1 и продолжается комбинацией ( k & minus; 1) ( V 2 *) 1044 *, V 3 , & hellip ;, V n ).
«Пропустить первый элемент». Комбинация представляет собой комбинацию k ( V i , V i + 1 , & hellip; V n ), где i - наименьший индекс, такой что V i & ne; * 1 087 * В 1 * ** тысячи девяносто-одна * тысячи девяносто-два. (Чтобы избежать дублирования, нам нужно пропустить всех элементов, идентичных первому элементу.)
Единственная разница здесь с биномиальной рекурсией - это использование индекса i во втором варианте; если в наборе нет повторяющихся элементов, это уменьшается до i & 2; это приводит к рекурсии C ( n , k ) = C ( n минус 1, k минус 1) + C ( n минус 1, k ).
Наивная реализация этой рекурсии займет экспоненциальное время, потому что каждое вычисление требует двух рекурсивных вызовов; тем не менее, существует только квадратичное количество уникальных вызовов, поэтому вычисление может быть сокращено до квадратичного времени путем запоминания или динамического программирования. В приведенном ниже решении используется динамическое программирование, поскольку для этого требуется только линейное пространство. (Для запоминания потребовалось бы квадратичное пространство, поскольку имеется подкадровое число подзадач.)
Решение динамического программирования инвертирует рекурсию, вычисляя количество k -комбинаций для последовательных суффиксов вектора. Необходимо сохранить значения только для двух суффиксов: предыдущего суффикса и предыдущего суффикса с другим первым элементом, соответствующим количеству, необходимому для первого и второго параметра приведенной выше рекурсии. (Фактический код использует префиксы вместо суффиксов, но это не имеет абсолютно никакого значения.)
В качестве незначительной оптимизации мы вычисляем только значения k -комбинаций для значений k между 0 и & lceil; n / 2 & rceil ;. Как и в случае с биномиальными коэффициентами, подсчет симметричен: число k -комбинаций равно количеству ( n & minus; k ) - комбинаций, поскольку каждый k -комбинация соответствует уникальной ( n & minus; k ) - комбинации, состоящей из всех невыбранных элементов. Дополнительная оптимизация возможна на основе того факта, что нам нужен только один счет в конце, но дополнительное усложнение только затеняет основной алгоритм.
Тот факт, что решение является O ( n 2 ), немного раздражает, но, поскольку n , как правило, будет небольшим числом (в противном случае считается будет астрономическим) время вычислений кажется разумным. Несомненно, возможны дальнейшие оптимизации, и вполне возможно, что существует субквадратичный алгоритм.
Вот базовая реализация на C (с использованием массива строк):
/* Given a *sorted* vector v of size n, compute the number of unique k-combinations
* of the elements of the vector for values of k between 0 and (n/2)+1.
* The counts are stored in the vector r, which must be large enough.
* Counts for larger values of k can be trivially looked up in the returned
* vector, using the identity r[k] == r[n - k].
* If v is not sorted, the result will be incorrect. The function does not
* check for overflow, but the results will be correct modulo (UINTMAX + 1)
*/
void multicomb(const char** v, size_t n, uintmax_t* r) {
size_t lim = n / 2 + 1;
// Prev retains the counts for the previous prefix ending with
// a different element
uintmax_t prev[lim];
// If there are no elements, there is 1 0-combination and no other combinations.
memset(r, 0, sizeof prev);
r[0] = 1;
// Iterate over the unique elements of v
for (size_t k = 0; k < n; ) {
// Save the counts for this prefix
memcpy(prev, r, sizeof prev);
// Iterate over the prefixes with the same ending value
do {
for (size_t i = lim - 1; i > 0; --i)
r[i] = r[i - 1] + prev[i];
} while (++k < n && strcmp(v[k - 1], v[k]) == 0);
};
}
По сравнению с решением в самоответе ОП, эта версия:
- переполняется позже, потому что это зависит только от сложения. (Тот факт, что нет деления, также значительно облегчает вычисление числа по модулю простого числа.)
- занимает квадратичное время вместо экспоненциального.