Элементы комбинаторики

Рандомайзер чисел. генератор случайных чисел без повторения.

Перестановки с повторениями

Особого внимания заслуживает задача генерации перестановок N элементов в случае если элементы последовательности могут повторяться. Допустим, исходная последовательность состоит из элементов n1, n2… nk, где элемент n1 повторяется r1 раз, n2 повторяется r2 раз и т.д. При этом n1+n2+…+nk=N.  Если мы будем считать все n1+n2+…+nk элементов перестановки с повторениями различными, то всего различных вариантов перестановок (n1+n2+…+nk)! . Однако среди этих перестановок не все различны. В самом деле, все r1 элементов n1 мы можем переставлять местами друг с другом, и от этого перестановка не изменится. Точно так же, можем переставлять элементы n2, n3 и т. д. В итоге имеем r1! вариантов записи одной и той же перестановки с различным расположением повторяющихся элементов n1. Таким образом, всякая перестановка может быть записана r1!·r2!·…·rk! способами. Следовательно, число различных перестановок с повторениями равно

Для генерации перестановок с повторениями можно использовать алгоритм генерации перестановок без повторений, приведенный выше. Введем повторяющийся элемент в массив a. Ниже приведен код программы для генерации перестановок с повторениями (изменен только код функции main()).

12345678910111213141516171819202122232425262728293031323334353637383940414243444546

#include <iostream>using namespace std;void swap(int *a, int i, int j){  int s = a;  a = a;  a = s;}bool NextSet(int *a, int n){  int j = n — 2;  while (j != -1 && a >= a) j—;  if (j == -1)    return false; // больше перестановок нет  int k = n — 1;  while (a >= a) k—;  swap(a, j, k);  int l = j + 1, r = n — 1; // сортируем оставшуюся часть последовательности  while (l<r)    swap(a, l++, r—);  return true;}void Print(int *a, int n)  // вывод перестановки{  static int num = 1; // номер перестановки  cout.width(3); // ширина поля вывода номера перестановки  cout << num++ << «: «;  for (int i = 0; i < n; i++)    cout << a << » «;  cout << endl;}int main() {  int n, *a;  cout << «N = «;  cin >> n;  a = new int;  for (int i = 0; i < n; i++)    a = i + 1;  a = 1; // повторяющийся элемент  Print(a, n);  while (NextSet(a, n))    Print(a, n);  cin.get(); cin.get();  return 0;}

Результат работы приведенного выше алгоритма:

Алгоритмизация

Оцените статью