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

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

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

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

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

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

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

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

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

Наприклад, із цифр 1, 2, 3, 4 можна скласти ${\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 5-7782-0332-2.

Див. також

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.