Размещение:Комбинаторика

В комбинаторике размещением называется расположение «предметов» на некоторых «местах» при условии, что каждое место занято в точности одним предметом и все предметы различны. Более формально, размеще́нием (из n по k) называется упорядоченный набор из k различных элементов некоторого n-элементного множества.

Например, $\langle 1,3,2,5\rangle$ — это 4-элементное размещение 6-элементного множества {1,2,3,4,5,6}.

В отличие от сочетаний размещения учитывают порядок следования предметов. Так, например, наборы < 2,1,3 > и < 3,2,1 > являются различными, хотя состоят из одних и тех же элементов {1,2,3} (то есть, совпадают как сочетания).

Количество размещений

Количество размещений из n по k, обозначаемое $A_n^k$, дается формулами:

$A_n^k = n(n-1)\cdots(n-k+1) = \frac{n!}{(n-k)!} = \binom{n}{k} k!.$

Последнее выражение имеет естественную комбинаторную интерпретацию: каждое размещение из n по k однозначно соответствует некоторому сочетанию из n по k и некоторой перестановке элементов этого сочетания; число сочетаний из n по k равно биномиальному коэффициенту $\binom{n}{k}$, в то время как перестановок на k элементах ровно k! штук.

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

Размещение с повторениями — это размещение предметов в предположении, что каждый предмет может участвовать в размещении сколь угодно раз. По правилу умножения количество размещений с повторениями из n по k равно n^k.

Например, количество вариантов 3-x значного кода, в котором каждый знак является цифрой от 0 до 9 и может повторяться, равно 10³ = 1000.

Пример алгоритма получения размещений с повторениями для массива объектов на Java

import java.util.Arrays;
 
public class PermutationsWithRepetition {
    private Object[] source;
    private int variationLength;
 
    public PermutationsWithRepetition(Object[] source, int variationLength) {
        this.source = source;
        this.variationLength = variationLength;
    }
 
    public Object[][] getVariations() {
        int srcLength = source.length;
        int permutations = (int) Math.pow(srcLength, variationLength);
 
        Object[][] table = new Object[permutations][variationLength];
 
        for (int i = 0; i < variationLength; i++) {
            int t2 = (int) Math.pow(srcLength, i);
            for (int p1 = 0; p1 < permutations;) {
                for (int al = 0; al < srcLength; al++) {
                    for (int p2 = 0; p2 < t2; p2++) {
                        table[p1][i] = source[al];
                        p1++;
                    }
                }
            }
        }
 
        return table;
    }
 
    public static void main(String[] args) {
        PermutationsWithRepetition gen = new PermutationsWithRepetition(
                new Integer[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 0},
                5);
 
        Object[][] variations = gen.getVariations();
 
        for (Object[] s : variations) {
            System.out.println(Arrays.toString(s));
        }
    }
}

Пример получения размещений с повторениями для списка на Haskell

import Control.Monad
permutationsWithRepetition xs = iterate (liftM2 (:) xs) [[]]
 
Prelude> take 4 (permutationsWithRepetition "ab")
[[""],["a","b"],["aa","ab","ba","bb"],["aaa","aab","aba","abb","baa","bab","bba","bbb"]]
Prelude> permutationsWithRepetition [1,2,3] !! 2
[[1,1],[1,2],[1,3],[2,1],[2,2],[2,3],[3,1],[3,2],[3,3]]

Ссылки

• Вычисление числа размещений онлайн