- Размещения
-
В комбинаторике размещением называется расположение «предметов» на некоторых «местах» при условии, что каждое место занято в точности одним предметом и все предметы различны. Более формально, размеще́нием (из n по k) называется упорядоченный набор из k различных элементов некоторого n-элементного множества.
Например, — это 4-элементное размещение 6-элементного множества {1,2,3,4,5,6}.
В отличие от сочетаний размещения учитывают порядок следования предметов. Так, например, наборы < 2,1,3 > и < 3,2,1 > являются различными, хотя состоят из одних и тех же элементов {1,2,3} (то есть, совпадают как сочетания).
Содержание
Количество размещений
Количество размещений из n по k, обозначаемое , дается формулами:
Последнее выражение имеет естественную комбинаторную интерпретацию: каждое размещение из n по k однозначно соответствует некоторому сочетанию из n по k и некоторой перестановке элементов этого сочетания; число сочетаний из n по k равно биномиальному коэффициенту , в то время как перестановок на k элементах ровно k! штук.
Размещение с повторениями
Размещение с повторениями — это размещение предметов в предположении, что каждый предмет может участвовать в размещении сколь угодно раз. По правилу умножения количество размещений с повторениями из n по k равно nk.
Например, количество вариантов 3-x значного кода, в котором каждый знак является цифрой от 0 до 9 и может повторяться, равно 103 = 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]]
Ссылки
- Вычисление числа размещений онлайн
Wikimedia Foundation. 2010.