ACM模版

描述

给出一个字符串S（可能又重复的字符），按照字典序从小到大，输出S包括的字符组成的所有排列。例如：S = “1312”，
输出为：

1123
1132
1213
1231
1312
1321
2113
2131
2311
3112
3121
3211

Input
输入一个字符串S（S的长度 <= 9，且只包括0 - 9的阿拉伯数字）

Output
输出S所包含的字符组成的所有排列

Input示例
1312

Output示例
1123
1132
1213
1231
1312
1321
2113
2131
2311
3112
3121
3211

题解

全排列问题，属于不重复排列。用一般的dfs算法解会
Time limit exceeded，原因很简单，复杂度太高了。所以不能用dfs，需要用一种比较原始的解法了。

代码

dfs超时代码：

#include <iostream>
#include <cstring>

using namespace std;

#define MAX_N 10

char nums[MAX_N];
int n, m;           // 共有n个数,其中互不相同的有m个
char rcd[MAX_N];    // 记录每个位置填的数
int used[MAX_N];    // 标记m个数可以使用的次数
char num[MAX_N];    // 存放输入中互不相同的m个数

void unrepeat_permutation(int l)
{
    int i;
    if (l == n)     // 填完了n个数,则输出
    {
        for (i = 0; i < n; i++)
        {
            printf("%c", rcd[i]);
        }
        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;
    char val;
    if (scanf("%s", nums) == EOF)
    {
        return 0;
    }
    n = (int)strlen(nums);
    m = 0;
    for (i = 0; i < n; i++)
    {
        val = nums[i];
        for (j = 0; j < m; j++)
        {
            if (num[j] == val)
            {
                used[j]++;
                break;
            }
        }
        if (j == m)
        {
            num[m] = val;
            used[m++] = 1;
        }
    }
    for (i = 0; i < m - 1; i++)
    {
        for (j = i + 1; j < m; j++)
        {
            if (num[i] > num[j])
            {
                swap(num[i], num[j]);
                swap(used[i], used[j]);
            }
        }
    }
    return 1;
}

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

大概有五六组数据爆掉了。
AC代码：

#include<stdio.h>
#include<string.h>
#include<algorithm>

using namespace std;

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

参考

排列组合