В комбінаториці, розміщенням із 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[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 5-7782-0332-2.
Див. також Редагувати
| Це незавершена стаття з математики. Ви можете допомогти проєкту, виправивши або дописавши її. |