全排列与组合

对n个元素进行全排列共n!个
先确定第1位(从1开始计数)，第1位有n种情况(排头元素分别与后续元素交换)
对后边n-1位进行全排列，确定第2位
对后面n-2位进行全排列，确定第3位
......
到最后一位时，因为只剩下一个元素，即只有一种情况。

#include

void swap(int& a, int& b)
{
    if (&a != &b)
    {
        a = a ^ b;
        b = a ^ b;
        a = a ^ b;
    }
}

void permutate(int arr[], int begin, int n, int& sum)
{
    if (begin+1 == n)
    {
        ++sum;
        for (int i = 0; i < n; ++i)
            std::cout << arr[i] << " ";
        std::cout << std::endl;
    }
    else
    {
        for (int i = begin; i < n; ++i)
        {
            swap(arr[begin], arr[i]);          // 交换
            permutate(arr, begin + 1, n, sum); // 递归
            swap(arr[begin], arr[i]);          // 复原
        }
    }
}

n个数中任意m个数的全排列，共n!/(n-m)!个
void permutate(int arr[], int begin, int n, int m, int& sum)
{
    if (begin == m)
    {
        ++sum;
        for (int i = 0; i < m; ++i)
            std::cout << arr[i] << " ";
        std::cout << std::endl;
    }
    else
    {
        for (int i = begin; i < n; ++i)
        {
            swap(arr[begin], arr[i]);
            permutate(arr, begin + 1, n, m, sum);
            swap(arr[begin], arr[i]);
        }
    }
}

若n元集合中存在第1类元素为m1个（同类或者重复），第2类元素为m2个，..... ，第k类元素为mk个；
除这些重复元素之外，其余元素彼此各异，那么这个集合上一共存在n!/(m1!m2!...mk!)种不同的排列。
核心思想:
(1)确定排头元素A
(2)确定后续待交换元素B
(3)判断[A,B)之间是否出现过B，若出现过，则跳过此元素，否则，继续交换，递归，复原操作

// if there has same value(arr[t]) among arr[begin] to arr[t-1] 
bool recur(int arr[], int begin, int t)
{
    for (int i = begin; i < t; ++i)
        if (arr[i] == arr[t])
            return true;

    return false;
}

void perm3(int arr[], int begin, int n, int& sum)
{
    if (begin+1 == n)
    {
        ++sum;
        for (int i = 0; i < n; ++i)
            std::cout << arr[i] << " ";
        std::cout << std::endl;
    }
    else
    {
        for (int i = begin; i < n; ++i)
        {
            if (!recur(arr, begin, i))
            {
                swap(arr[begin], arr[i]);
                perm3(arr, begin + 1, n, sum);
                swap(arr[begin], arr[i]);
            }
        }
    }
}

int main()
{
    int arr[] = {1, 2, 3};
    int sum1 = 0, sum2 = 0, sum3 = 0;
    int n = sizeof(arr) / sizeof(int), m = 2;
    permutate(arr, 0, n, sum1);
    std::cout << sum1 << std::endl;
    std::cout << "choose " << m << " data from " << n << " data" << std::endl;
    permutate(arr, 0, n, m, sum2);
    std::cout << sum2 << std::endl;
    std::cout << "test duplicate numbers" << std::endl;
    int arr3[] = { 1, 1, 2};
    n = sizeof(arr3) / sizeof(int);
    perm3(arr3, 0, n, sum3);
    std::cout << sum3 << std::endl;

    return 0;
}

1 2 3
1 3 2
2 1 3
2 3 1
3 2 1
3 1 2
6
choose 2 data from 3 data
1 2
1 3
2 1
2 3
3 2
3 1
6
test duplicate numbers
1 1 2
1 2 1
2 1 1
3

n个数中任意m个数的组合，共n!/(m!(n-m)!)个
n个数的全子集类似n位二进制数中1的位置与数量
组合问题可转化为n位二进制数中1的数量为m的问题。

#include

int comb(int n, int m)
{
    int sum = 0, t = 0, num = 0;
    for (int i = 0; i < (1 << n); ++i)
    { 

        t = i;
        num = 0;
        // 计算n位二进制数中1的个数
        while (t)
        {
            t = t & (t - 1);
            ++num;
        }

        if (num == m)
        {
            for (int j = 0; j < n; ++j)
                if (i & (1 << j))
                    std::cout << j << " ";
            std::cout << std::endl;
            ++sum;
        }
    }

    return sum;
}

int main()
{
    std::cout << comb(6, 5) << std::endl;

    return 0;
}

0 1 2 3 4
0 1 2 3 5
0 1 2 4 5
0 1 3 4 5
0 2 3 4 5
1 2 3 4 5
6