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

В комбінаториці, розміщенням із 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}}}$.

Кількість розміщень із 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++;                 }             }         } 

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

Це незавершена стаття з математики. Ви можете допомогти проєкту, виправивши або дописавши її.