В комбінаториці, розміщенням із n елементів по m, або впорядкованою (n, m) вибіркою із множини M (потужність n, m≤n) називають довільний кортеж що складається із m попарно відмінних елементів. Розміщення можна розглядати як різнозначну функцію f: , для якої .

Кількість розміщень із n по m позначається як або і обчислюється за такою формулою:

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

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

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

Наприклад, із цифр 1, 2, 3, 4 можна скласти трьохзначних числа.

Приклад алгоритму отримання розміщень з повторюваннями на С #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;

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 = ++index; if (index >= alphabet.Length) index = 0; // додається результат до колекції yield return target; iteration++;

Див. також

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

Джерела