STEP BY STEP

生成排列的算法(POJ - 1256 和 POJ百练 - 1833)

发表于 分类于 ， 阅读次数： Valine：
本文字数： 3.1k 阅读时长 ≈ 3 分钟

题目1描述:
输入:一个序列s,该序列里面可能会有同样的字符,不一定有序
输出:打乱输入中的序列,可能产生的所有新的序列
题目2描述:

输入:一个序列s,该序列里面可能会有同样的字符,不一定有序 和 一个整数k
输出:该序列往后计算第k个序列,所有序列是以字典序排序的如果会有序搜索的童鞋自然而然能立刻做出来第一个题目,可是第二个题目在s较长的情况下,却需要用模拟而不是搜索…
大家都知道STL里面有个泛函模版, prev_permutation和next_permutation,用法也很简单,实现的就是题目2的功能…
但是算法最好得靠自己想出来,自己想出来的才是自己的,碰到新的问题才能产生思想的火花…废话少说,题目1的解法就是深搜,不过需要加上一个bool数组标记和一个函数确定不同字符之间的大小(有可能这个大小还不是Ascii码就能决定的),
大致描述下搜索过程,比如输入序列是12345,那么我搜索的过程大致是第一层按顺序选取1-5,进入第二层的时候也是按顺序选取1-5,
以此类推,但是每一层里面都只能选前面的层次没有选过的数,而且因为有重复字符,算法还必须保证每一层里面按顺序选取的字符必须是升序的,
熟悉顺序搜索和回溯的同学,很自然就会产生这样的想法…
POJ - 1256的代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <stdlib.h>
#include <algorithm>
#define MAX (13 + 10)
using namespace std;
bool bUsed[MAX];
char szAns[MAX];
char szInput[MAX];
bool CmpChar(char chOne, char chTwo)
{
    if (abs(chOne - chTwo) != 'a' - 'A')
    {
        return tolower(chOne) - tolower(chTwo) < 0;
    }
    return chOne - chTwo < 0;
} 

bool Greater(char chOne, char chTwo) 
{ 
    if (abs(chOne - chTwo) != 'a' - 'A') 
    { 
        return tolower(chOne) - tolower(chTwo) > 0;
    }
    return chOne - chTwo > 0;
}

void Gen(int nDepth, int nLen)
{
    if (nDepth == nLen)
    {
        szAns[nLen] = '\0';
        printf("%s\n", szAns);
        return;
    }

    char chLast = '\0';
    for (int i = 0; i < nLen; ++i)
    {
        if (!bUsed[i] && Greater(szInput[i], chLast))
        {
            bUsed[i] = true;
            szAns[nDepth] = szInput[i];
            Gen(nDepth + 1, nLen);
            bUsed[i] = false;
            chLast = szInput[i];
        }
    }
}
int main()
{
    int nCases;

    scanf("%d", &nCases);
    while (nCases--)
    {
        scanf("%s", szInput);
        int nLen = strlen(szInput);
        sort(szInput, szInput + nLen, CmpChar);
        Gen(0, nLen);
    }

    return 0;
}

题目2的解法是模拟,功能类似与STL的那2个泛型模版函数,算法的大致过程是想办法从当前序列进入下一个刚好比其大或者刚好比其小的序列…很自然我们想到要把序列后面大的字符交和前面小的字符交换就会使序列变大,为了使其刚好变大,可以把交换后的字符从交换位置起至最后都排序一下,现在的问题是我们如何选取2个字符交换…正确的想法是,我们从最后面开始往前面看,寻找一个最长的递增序列,找到之后,我们只需要选取递增序列前面的那个字符chBefore和递增序列里面的一个最小的比chBefore大的字符交换即可…交换之后,将新的递增序列排序一下即可…
为什么这样做了,因为从后往前看的递增序列,是不能交换2个字符让当前序列变大的,所以必须选取最长递增序列前面的那个字符交换…

POJ百练 - 1833 的代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define MAX (1024 + 10)
using namespace std;
int nInput[MAX];
void GetNext(int* nInput, int nLen)
{
    int i = nLen - 2;
    while (i >= 0)
    {
        if (nInput[i] >= nInput[i + 1])
        {
            --i;
        }
        else
        {
            int k = i + 1;
            for (int j = nLen - 1; j > i; --j)
            {
                if (nInput[j] > nInput[i] && nInput[j] < nInput[k])
                {
                    k = j;
                }
            }
            swap(nInput[i], nInput[k]);
            sort(nInput + i + 1, nInput + nLen);
            return;
        }
    }

    sort(nInput, nInput + nLen);
}
int main()
{
    int nCases;
    scanf("%d", &nCases);
    while (nCases--)
    {
        int nLen;
        int nK;
        scanf("%d%d", &nLen, &nK);
        for (int i = 0; i < nLen; ++i)
        {
            scanf("%d", &nInput[i]);
        }
        for (int i = 0; i < nK; ++i)
        {
            GetNext(nInput, nLen);
        }
        for (int i = 0; i < nLen; ++i)
        {
            printf("%d%s", nInput[i], i == nLen - 1 ? "\n" : " ");
        }
    }
    return 0;
}