Розміщення (комбінаторика)

У Вікіпедії є статті про інші значення цього терміна: Розміщення.

В комбінаториці, розміщенням із n елементів по m, або впорядкованою (n, m) вибіркою із множини M (потужність n, m≤n) називають довільний кортеж ${\displaystyle (a_{i_{1}},a_{i_{2}},\dots ,a_{i_{m}})}$ що складається із m попарно відмінних елементів. Розміщення можна розглядати як різнозначну функцію f: ${\displaystyle {1,2,\dots ,m}\to M}$, для якої ${\displaystyle f(j)=a_{i_{j}}}$.

Всі 60 варіантів розміщення 3 із 5.

Кількість розміщень із n по m позначається як ${\displaystyle A_{n}^{m}}$ або ${\displaystyle P(n,m)}$ і обчислюється за такою формулою:

${\displaystyle A_{n}^{m}=n(n-1)\dots (n-m+1)={\frac {n!}{(n-m)!}}}$

Розміщення з повтореннями

Розміщенням з повтореннями із n елементів по m або впорядкованою (n, m) вибіркою з поверненнями називається довільний кортеж ${\displaystyle (a_{1},\dots ,a_{m})}$ елементів множини M, для якого |M| = n.

Кількість можливих розміщень з повтореннями із n елементів по m дорівнює n піднесене до степеня m:

${\displaystyle {\hat {P}}(n,m)=n^{m}}$

Наприклад, із цифр 1, 2, 3, 4 можна скласти ${\displaystyle {\hat {P}}(4,3)=4^{3}=64}$ трьохзначних числа.

Приклад алгоритму отримання розміщень з повторюваннями на С

#include <stdio.h> #include <math.h> int main(int argc, char* argv[]) { const int len = 4;// довжина розміщення char elements[] = {'0', '1'};// елементи в розміщенні int els = (int)(sizeof(elements) / sizeof(char)); // кількість розміщень int permutations = (unsigned int) pow((double)els, len); char **table = new char *[permutations]; for(int i = 0; i < permutations; ++i) table[i] = new char[4]; for (int i = 0; i < len; i++) { int t = (int) pow((double)els, i); for (int position_i = 0; position_i < permutations;) for (int el_num = 0; el_num < els; el_num++) for (int repeats = 0; repeats < t; repeats++) { table[position_i][i] = elements[el_num]; position_i++; } } // виведення результату у консоль for (int i = 0; i < permutations; i++) { printf("%3d - ", i + 1); for (int j = 0; j < len; j++) printf("%c ", table[i][j]); printf("\n"); } return 0; } 

Приклад алгоритму отримання розміщень з повторюваннями на С#

 /// <summary>  ///   /// </summary>  /// <param name="length">Довжина розміщення</param>  /// <param name="alphabet">Абетка</param>  /// <returns></returns>  public IEnumerable<string> Bruteforce(int length, string alphabet)  {  if (length > 0 && alphabet != null)  {  int[] indexes = new int[length];  int index = 0;  int iteration = 0;  // кількість розміщень  var permutations = Math.Pow(alphabet.Length, length);  while (iteration < permutations)  {  var target = alphabet[index].ToString();  // перераховуються перестановки  for (int i = 1; i < length; i++)  {  if (indexes[i - 1] >= alphabet.Length)  {  indexes[i]++;  indexes[i - 1] = 0;  }  target += alphabet[indexes[i] < alphabet.Length ? indexes[i] : 0];  }  indexes[0] = ++index;  if (index >= alphabet.Length) index = 0;  // додається результат до колекції  yield return target;  iteration++;  }  }  } 

Джерела інформації

• Судоплатов С. В., Овчинникова Е. В. (2002). Элементы дискретной математики. НГТУ. ISBN .

Див. також

• Перестановка
• Підстановка
• Комбінація