Функция для определения количества незаказанных комбинаций с non-unqiue выбором
Я пытаюсь определить функцию для определения количества незаказанных комбинаций с групповым выбором.
Данный:
n = number of unique symbols to select from
r = number of choices
Пример... для n=3, r=3, результат был бы: (редактирование: добавленные отсутствующие значения, на которые указывает Dav)
000
001
002
011
012
022
111
112
122
222
Я знаю формулу для перестановок (незаказанный, уникальные выборы), но я не могу выяснить, как разрешение повторения увеличивает набор.
2 ответа
Если у Вас есть N уникальные символы, и Вы хотите выбрать комбинацию длины R, то Вы, по сути, помещаете N-1 разделители в R+1 "слоты" между совокупным количеством выбранных символов.
0 [C] 1 [C] 2 [C] 3
С - это выбор, числа - это совокупное количество выбранных на данный момент символов. По сути, вы ставите разделитель для каждой возможной вещи, которую вы могли выбрать, когда "начинаете" выбирать эту вещь (предполагается, что вы начинаете с выбора определенной вещи до того, как будут помещены какие-либо разделители, отсюда и -1 в разделителях N-1).
Если вы ставите все разделители в точку 0, то вы выбираете конечную вещь для всех вариантов выбора. Если вы поместите все разделители в точку 3, то вы выберете исходную вещь для всех вариантов выбора. В общем, если вы поместите разделитель с на место k, то вы выбрали вещь i+1 для всех вариантов выбора, которые приходят между этим местом и местом следующего разделителя.
Так как мы пытаемся поставить N-1 не унифицированные элементы (делители не унифицированы, это просто делители) вокруг слотов R, мы действительно просто хотим прослушать N-1 1's и R 0's, т.е. фактически
(N+R-1) выбираем (N-1) =(N+R-1)! /((N-1)!R!).
Таким образом, окончательная формула - (N+R-1)!/((N-1)!R!) для количества неупорядоченных комбинаций с неуникальным выбором элементов.
Обратите внимание, что для N=3, R=3 это значение равно 10, что совпадает с вашим результатом... после добавления недостающих опций, на которые я указал в комментариях выше.
.В C ++ дана следующая процедура:
template <typename Iterator>
bool next_combination(const Iterator first, Iterator k, const Iterator last)
{
/* Credits: Mark Nelson http://marknelson.us */
if ((first == last) || (first == k) || (last == k))
return false;
Iterator i1 = first;
Iterator i2 = last;
++i1;
if (last == i1)
return false;
i1 = last;
--i1;
i1 = k;
--i2;
while (first != i1)
{
if (*--i1 < *i2)
{
Iterator j = k;
while (!(*i1 < *j)) ++j;
std::iter_swap(i1,j);
++i1;
++j;
i2 = k;
std::rotate(i1,j,last);
while (last != j)
{
++j;
++i2;
}
std::rotate(k,i2,last);
return true;
}
}
std::rotate(first,k,last);
return false;
}
Затем вы можете перейти к следующему:
std::string s = "12345";
std::size_t r = 3;
do
{
std::cout << std::string(s.begin(),s.begin() + r) << std::endl;
}
while(next_combination(s.begin(), s.begin() + r, s.end()));