Permutations and Combinations

基本概念以及生成下一个排列、组合的算法整理。
参考：Discrete mathematics and its applications

Basic Using

Permutation

• permutation : an ordered arrangement of the elements of a set
• r-permutation : an ordered arrangement of r elements of a set
• The number of r-permutations of a set with n distinct elements is P(n, r) = n(n-1)(n-2)…(n-r+1) = n!/(n-r)!

Permutations With Repetition

• The number of r-permutations of a set of n objects with repetition allowed is n^r

Permutations of Sets With Indistinguishable Objects

• Consider the situation: n-Permutation with limited repetition, A = { n1*a1 ,n2 a2 ,…,nkak } ，where n1+n2+…+nk = n. The number of different permutations of n objects, where there are n1 indistinguishable objects of type1,…,and nk indistinguishable objects of type k, is n!/(n1!n2!…nk!)

Combitation

• r-combination : an unordered selection of r elements of a set
• The number of r-combination of a set with n elements is C(n, r) = n(n-1)(n-2)…(n-r+1)/r! = n!/(n-r)!/r!
• Let n and r be nonnegative integers with r <= n. Then C(n ,r) = C(n, n-r)

Combination With Repetition

• There are C (n-1+r, r) r-combination from a set with n elements when repetition of elements is allowed.

• Proof : 从n个不同的元素中选出r个可重复元素的排列，可以看成：用n-1个竖线，分隔开r个元素的问题，比如 * * | * | * 代表从3个不同的元素中选出4个元素。所以问题就转换成n-1 + r个位置中选n-1个作为竖线，其他r个作为元素。就是C(n-1+r,n-1) = C(n-1+r,r)

Generating Permutations and Combinations

Generating Permutations

• Algorithm of producing the n! permutations of the integers 1, 2, …, n:

1. Begin with the smallest permutation in lexicographic order, namely 1, 2, 3, 4,…, n.
2. Produce the next largest permutation.
3. Continue until all n! permutations have been found.

• Given permutation a1,a2,…,an, find the next largest permutation in increasing order:

1. Find the integers aj,aj+1 with aj < aj+1 and aj+1 > aj+2 > ... > an
2. Put in the jth position the least integer among aj+1,aj+2,...,an that is greater than aj
3. List in increasing order the rest of the integers aj,aj+1,...,an

For example, the next largest permutation in lexicographic order after 124653 is 125346.

Generating Combinations

How to generate all combinations of the elements of a finite set ?
A combination is just a subset. Use bit strings of length n to represent a subset of a set with n elements. So we need to list all bit strings of length n.

• Algorithm of Producing All Bit Strings of length n

1. Start with the bit string 000…00,with n zeros.
2. Then, successively find the next largest expansion until the bit string 111…11 is obtained.

• Algorithm of finding the next largest binary expansion

Locate the first position from the right that is not a 1, then changing all the 1s to the right of this position to 0s and making this first 0 a 1.(实际上就是加一)

For example: 1000110011 -> 1000110100

• Algorithm for generating the r-combination of the set {1, 2, …, n}

1. S1 = {1, 2, …, r}
2. If Si = {a1,a2,...,ar} 1<=i<=C(n,rh-1 has found, then the next combination can be obtained using the following rules: First, locate the last element ai in the sequence such that ai != n-r+i. Then replace ai with ai + 1 and aj with ai + j - i + 1, for j = i+1,i+2,...,r.

For example: Si ={2,3,5,6,9,10} is given.Then Si+1 ={2,3,5,7,8,9}.