排列组合

ACM模版

排列

类循环排列

用递归实现多重循环,本递归程序相当于n重循环,每重循环的长度为m的情况,所以输出共有m^n行。

/* * 输入样例: 3 2 * 输出样例: * 0 0 0 * 0 0 1 * 0 1 0 * 0 1 1 * 1 0 0 * 1 0 1 * 1 1 0 * 1 1 1 */
#define MAX_N 10
int n, m;                       // 相当于n重循环,每重循环长度为m
int rcd[MAX_N];                 // 记录每个位置填的数
void loop_permutation(int l)
{
    int i;
    if (l == n)                 // 相当于进入了 n 重循环的最内层
    {
        for (i = 0; i < n; i++)
        {
            cout << rcd[i];
            if (i < n-1)
            {
                cout << " ";
            }
        }
        cout << "\n";
        return ;
    }
    for (i = 0; i < m; i++)     // 每重循环长度为m
    {
        rcd[l] = i;             // 在l位置放i
        loop_permutation(l + 1);  // 填下一个位置
    }
}

int main()
{
    while (cin >> n >> m)
    {
        loop_permutation(0);
    }
    return 0;
}

全排列

dfs即可……

/* * 对输入的n个数作全排列。 * 输入样例: * 3 * 1 2 3 * 输出样例: * 123 * 132 * 213 * 231 * 312 * 321 */
#define MAX_N 10
int n;                      // 共n个数
int rcd[MAX_N];             // 记录每个位置填的数
int used[MAX_N];            // 标记数是否用过
int num[MAX_N];             // 存放输入的n个数

void full_permutation(int l)
{
    int i;
    if (l == n)
    {
        for (i = 0; i < n; i++)
        {
            printf("%d", rcd[i]);
            if (i < n-1)
            {
                printf(" ");
            }
        }
        printf("\n");
        return ;
    }
    for (i = 0; i < n; i++)         // 枚举所有的数(n个),循环从开始
        if (!used[i])
        {                           // 若num[i]没有使用过, 则标记为已使用
            used[i] = 1;
            rcd[l] = num[i];        // 在l位置放上该数
            full_permutation(l+1);  // 填下一个位置
            used[i] = 0;            // 清标记
        }
}

int read_data()
{
    int i;
    if (scanf("%d", &n) == EOF)
    {
        return 0;
    }
    for (i = 0; i < n; i++)
    {
        scanf("%d", &num[i]);
    }
    for (i = 0; i < n; i++)
    {
        used[i] = 0;
    }
    return 1;
}

int main()
{
    while (read_data())
    {
        full_permutation(0);
    }
    return 0;
}

程序通过used数组,标记数是否被用过,可以产生全排列,共有n!种。但是, 通过观察会发现,若输入的n个数有重复,那么在输出的n!种排列中,必然存在重复的项,若不允许输出重复的项,该怎么做呢?

不重复排列

DFS解法：

/* * 输入n个数,输出由这n个数构成的排列,不允许出现重复的项。 * 输入样例: * 3 * 1 1 2 * 输出样例: * 1 1 2 * 1 2 1 * 2 1 1 */
#define MAX_N 10
int n, m;           // 共有n个数,其中互不相同的有m个
int rcd[MAX_N];     // 记录每个位置填的数
int used[MAX_N];    // 标记m个数可以使用的次数
int num[MAX_N];     // 存放输入中互不相同的m个数

void unrepeat_permutation(int l)
{
    int i;
    if (l == n)     // 填完了n个数,则输出
    {
        for (i = 0; i < n; i++)
        {
            printf("%d", rcd[i]);
            if (i < n - 1)
            {
                printf(" ");
            }
        }
        printf("\n");
        return ;
    }
    for (i = 0; i < m; i++)             // 枚举m个本质不同的数
    {
        if (used[i] > 0)                // 若数num[i]还没被用完,则可使用次数减
        {
            used[i]--;
            rcd[l] = num[i];            // 在l位置放上该数
            unrepeat_permutation(l+1);  // 填下一个位置
            used[i]++;                  // 可使用次数恢复
        }
    }
}

int read_data()
{
    int i, j, val;
    if (scanf("%d", &n) == EOF)
    {
        return 0;
    }
    m = 0;
    for (i = 0; i < n; i++)
    {
        scanf("%d", &val);
        for (j = 0; j < m; j++)
        {
            if (num[j] == val)
            {
                used[j]++; break;
            }
        }
        if (j == m)
        {
            num[m] = val;
            used[m++] = 1;
        }
    }
    return 1;
}

int main()
{
    while (read_data())
    {
        unrepeat_permutation(0);
    }
    return 0;
}

本程序将全排列中的used标记数组改为记录输入中每个本质不同的数出现的次数,并在递归函数中使用。需要注意的是,在输入过程中,应剔除重复的数值。实际上,重复排列的产生是由于同一个位置被多次填入了相同的数,并且这多次填入又是在同一次循环过程中完成的。本方法通过统计每个本质不同的数的个数,使得循环长度由n变为m,这样,i一旦自增,就再也不会指向原先填入过的数了。这种方法剪去了重复项的生成,从而加快了搜索速度,是深度优先搜索中常用的剪枝技巧。

规律性解法：

int main()
{
    char ch[10];
    scanf("%s",ch);
    int len = (int)strlen(ch);
    sort(ch, ch + len);

    int cnt;
    do
    {
        printf("%s\n", ch);
        cnt = -1;
        for (int i = len - 1; i > 0; i--)
        {
            if (ch[i] > ch[i - 1])
            {
                cnt = i - 1;
                for (int j = len - 1; j >= 0; j--)
                {
                    if (ch[j] > ch[cnt])
                    {
                        char tmp = ch[j] ^ ch[cnt];
                        ch[j] ^= tmp;
                        ch[cnt] ^= tmp;
                        for (int k = i; k <= (i + len - 1) / 2; k++)    // ch[cnt]和ch[j]置换后变大，后边的为递
                        {                                               // 减，所以需要倒置，变为递增
                            tmp = ch[k] ^ ch[len - 1 + i - k];
                            ch[k] ^= tmp;
                            ch[len - 1 + i - k] ^= tmp;
                        }
                        break;
                    }
                }
                break;
            }
        }
    } while (cnt != -1);

    return 0;
}

组合

一般组合

/* * 输入n个数,从中选出m个数可构成集合,输出所有这样的集合。 * 输入样例: * 4 3 * 1 2 3 4 * 输出样例: * 1 2 3 * 1 2 4 * 1 3 4 * 2 3 4 */
#define MAX_N 10
int n, m;       // 从n个数中选出m个构成组合
int rcd[MAX_N]; // 记录每个位置填的数
int num[MAX_N]; // 存放输入的n个数

void select_combination(int l, int p)
{
    int i;
    if (l == m) // 若选出了m个数, 则打印
    {
        for (i = 0; i < m; i++)
        {
            printf("%d", rcd[i]);
            if (i < m - 1)
            {
                printf(" ");
            }
        }
        printf("\n");
        return ;
    }
    for (i = p; i < n; i++) // 上个位置填的是num[p-1],本次从num[p]开始试探
    {
        rcd[l] = num[i];    // 在l位置放上该数
        select_combination(l + 1, i + 1);   // 填下一个位置
    }
}

int read_data()
{
    int i;
    if (scanf("%d%d", &n, &m) == EOF)
    {
        return 0;
    }
    for (i = 0; i < n; i++)
    {
        scanf("%d", &num[i]);
    }
    return 1;
}

int main()
{
    while (read_data())
    {
        select_combination(0, 0);
    }
    return 0;
}

因为在组合生成过程中引入了变量 p,保证了每次填入的数字在num中的下标是递增的,所以不需要使用used进行标记,共C(n, m)种组合。

全组合

/* * 输入n个数,求这n个数构成的集合的所有子集。 * 输入样例: * 3 * 1 2 3 * 输出样例: * 1 * 1 2 * 1 2 3 * 1 3 * 2 * 2 3 * 3 */
#define MAX_N 10
int n;          // 共n个数
int rcd[MAX_N]; // 记录每个位置填的数
int num[MAX_N]; // 存放输入的n个数

void full_combination(int l, int p)
{
    int i;
    for (i = 0; i < l; i++)             // 每次进入递归函数都输出
    {
        printf("%d", rcd[i]);
        if (i < l-1)
        {
            printf(" ");
        }
    }
    printf("\n");
    for (i = p; i < n; i++)             // 循环同样从p开始,但结束条件变为i>=n
    {
        rcd[l] = num[i];                // 在l位置放上该数
        full_combination(l + 1, i + 1); // 填下一个位置
    }
}

int read_data()
{
    int i;
    if (scanf("%d", &n) == EOF)
    {
        return 0;
    }
    for (i = 0; i < n; i++)
    {
        scanf("%d", &num[i]);
    }
    return 1;
}

int main()
{
    while (read_data())
    {
        full_combination(0, 0);
    }
    return 0;
}

全组合,共2^n种,包含空集和自身。与全排列一样,若输入的n个数有重复, 那么在输出的2^n种组合中,必然存在重复的项。避免重复的方法与不重复排列算法中使用的类似。

不重复组合

/* * 输入n个数,求这n个数构成的集合的所有子集,不允许输出重复的项。 * 输入样例: * 3 * 1 1 3 * 输出样例: * 1 * 1 1 * 1 1 3 * 1 3 * 3 */
#define MAX_N 10
int n, m;           // 输入n个数,其中本质不同的有m个
int rcd[MAX_N];     // 记录每个位置填的数
int used[MAX_N];    // 标记m个数可以使用的次数
int num[MAX_N];     // 存放输入中本质不同的m个数

void unrepeat_combination(int l, int p)
{
    int i;
    for (i = 0; i < l; i++)     // 每次都输出
    {
        printf("%d", rcd[i]);
        if (i < l - 1)
        {
            printf(" ");
        }
    }
    printf("\n");
    for (i = p; i < m; i++)     // 循环依旧从p开始,枚举剩下的本质不同的数
    {
        if (used[i] > 0)        // 若还可以用, 则可用次数减
        {
            used[i]--;
            rcd[l] = num[i];    // 在l位置放上该
            unrepeat_combination(l+1, i);   // 填下一个位置
            used[i]++;          //可用次数恢复
        }
    }
}

int read_data()
{
    int i, j, val;
    if (scanf("%d", &n) == EOF)
    {
        return 0;
    }
    m = 0;
    for (i = 0; i < n; i++)
    {
        scanf("%d", &val);
        for (j = 0; j < m; j++)
        {
            if (num[j] == val)
            {
                used[j]++;
                break;
            }
        }
        if (j == m)
        {
            num[m] = val;
            used[m++] = 1;
        }
    }
    return 1;
}

int main()
{
    while (read_data())
    {
        unrepeat_combination(0, 0);
    }
    return 0;
}

需要注意的是递归调用时,第二个参数是i,不再是全组合中的i+1!

应用

搜索问题中有很多本质上就是排列组合问题,只不过加上了某些剪枝和限制条件。解这类题目的基本算法框架常常是类循环排列、全排列、一般组合或全组 合。而不重复排列与不重复组合则是两种非常有效的剪枝技巧。