基本概念以及生成下一个排列、组合的算法整理。
参考：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 ,…,nk*ak }，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.

Implementation

#include <iostream>
#include <vector>
#include <algorithm>

using std::cout;
using std::endl;
using std::vector;
using std::reverse;
using std::cin;

namespace m{
template <typename _BidirectionalIterator>
struct compare_func {
    bool operator()(_BidirectionalIterator l, _BidirectionalIterator r) const noexcept {
        return *l < *r;
    }
};

template <typename _BidirectionalIterator>
struct swap_func {
    void operator()(_BidirectionalIterator l, _BidirectionalIterator r) const noexcept {
        auto tmp = *l;
        *l = *r;
        *r = tmp;
    }
};


template <
    typename _BidirectionalIterator,
    typename _Compare = compare_func<_BidirectionalIterator>,
    typename _Swap = swap_func<_BidirectionalIterator>
>
bool next_permutation(
        _BidirectionalIterator first, 
        _BidirectionalIterator last, 
        _Compare comp = compare_func<_BidirectionalIterator>(),
        _Swap swap = swap_func<_BidirectionalIterator>()){
    if (first == last) {
        return false;
    }
    auto it1 = first;
    ++it1;
    if (it1 == last) {
        return false;
    }
    it1 = last;
    --it1;
    decltype(it1) it2;
    while(it1 != first) {
        it2 = it1;
        --it2;
        if (comp(it2, it1)) {
            auto it3 = last;
            while(!comp(it2,--it3)) {
            }
            swap(it2, it3);
            reverse(it1, last);
            return true;
        }else{
            --it1;
        }
    }
    reverse(first, last);
    return false;
}
}


int main(int argc, char** argv) {
    auto dump = [](auto b, auto e) -> void{
        for(auto i=b;i!=e;i++){
            cout<<*i<<" ";
        }
        cout<<endl;
    };
    int n;
    cin>>n;
    vector<int> arr;
    for(int i =1;i<=n;i++){
        arr.push_back(i);
    }
    while(m::next_permutation(arr.begin(),arr.end())) {
        dump(arr.begin(),arr.end());
    }
    dump(arr.begin(), arr.end());
}

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}.