Функция для определения количества неупорядоченных комбинаций с неуникальными вариантами - PullRequest
Новая
       24

Функция для определения количества неупорядоченных комбинаций с неуникальными вариантами

5 голосов
/ 25 декабря 2009

Я пытаюсь определить функцию для определения количества неупорядоченных комбинаций с неуникальными вариантами.

Дано: 

n = number of unique symbols to select from
r = number of choices

Пример ... для n = 3, r = 3, результат будет: (правка: добавлены отсутствующие значения, отмеченные Давом) 

000
001
002
011
012
022
111
112
122
222

Я знаю формулу для перестановок (неупорядоченные, уникальные выборки), но я не могу понять, как допуск повторения увеличивает набор.

Ответы [ 2 ]

7 голосов
/ 13 апреля 2010

В 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()));
3 голосов
/ 25 декабря 2009

Если у вас есть N уникальные символы и вы хотите выбрать комбинацию длины R, то вы, по сути, помещаете N-1 разделители в R+1 «слоты» между совокупным общим количеством выбранных символов. 

0 [C] 1 [C] 2 [C] 3

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

Если вы поместите все делители на точку 0, то вы выбрали последнюю вещь для всех вариантов. Если вы разместите все делители на месте 3, то вы выберете начальную вещь для всех вариантов. В общем, если вы поместите делитель ith в точку k , то вы выберете вещь i + 1 для всех вариантов, которые находятся между этим местом и пятно следующего делителя.

Поскольку мы пытаемся поместить N-1 неуникальные предметы (делители не уникальны, они просто делители) вокруг R слотов, мы действительно просто хотим переставить N-1 1 и R 0, что эффективно

(N+R-1) choose (N-1) = (N+R-1)!/((N-1)!R!).

Таким образом, окончательная формула равна (N+R-1)!/((N-1)!R!) для числа неупорядоченных комбинаций с неуникальным выбором элементов.

Обратите внимание, что это значение равно 10 для N = 3, R = 3, что соответствует вашему результату ... после добавления недостающих опций, которые я указал в комментариях выше.

...