全排列
in LeetCode with 0 comment

全排列

?> with 0 comment

全排列算法 -- 递归&字典序实现

递归

1554097121.png

不去重

#include<iostream>
#include<vector>
using namespace std;
vector<vector<int>> ans;

void swap(vector<int>& Temp_array,int a,int b) {
    int temp = Temp_array[a];
    Temp_array[a] = Temp_array[b];
    Temp_array[b] = temp;
}

void fullArray(vector<int>& Array, int cursor, int end) {
    if (cursor == end) {
        ans.push_back(Array);
    }
    else {
        for (int i = cursor; i < end; i++) {
            swap(Array, cursor, i);
            fullArray(Array, cursor + 1, end);
            swap(Array, cursor, i);
        }
    }
}

int main() {
    vector<int> data = {1,2,3};
    fullArray(data, 0, 3);
    for (vector<int> i: ans) {
        for (int j : i) {
            cout << j;
        }
        cout << endl;
    }
    return 0;
}

输出为:

123
132
213
231
321
312

去重的全排列

如果我们输入的是abb,如果第二个字符和第三个交换,就会出现重复的结果。

去重的思路

去重的全排列就是从第一个数字起每个数分别与它后面非重复出现的数字交换。

用编程的话描述就是第i个数与第j个数交换时,要求[i,j)中没有与第j个数相等的数。

#include<iostream>
#include<vector>
using namespace std;
vector<vector<int>> ans;

void swap(vector<int>& Temp_array,int a,int b) {
    int temp = Temp_array[a];
    Temp_array[a] = Temp_array[b];
    Temp_array[b] = temp;
}

//在 Temp_array 数组中,[start,end) 中是否有与 str[end] 元素相同的
bool isswap(vector<int>& Temp_array, int start, int end) {
    for (; start < end; start++) {
        if (Temp_array[start] == Temp_array[end])
            return false;            
    }
    return true;
}
void fullArray(vector<int>& Array, int cursor, int end) {
    if (cursor == end) {
        ans.push_back(Array);
    }
    else {
        for (int i = cursor; i < end; i++) {
            if (isswap(Array, cursor, i)) {
                swap(Array, cursor, i);
                fullArray(Array, cursor + 1, end);
                swap(Array, cursor, i);
            }
        }
    }
}

int main() {
    vector<int> data = {1,2,2};
    fullArray(data, 0, 3);
    for (vector<int> i: ans) {
        for (int j : i) {
            cout << j;
        }
        cout << endl;
    }
    return 0;
}

全组合

如果不是求字符的所有排列,而是求字符的所有组合应该怎么办呢?还是输入三个字符 a、b、c,则它们的组合有a b c ab ac bc abc。当然我们还是可以借鉴全排列的思路,利用问题分解的思路,最终用递归解决。不过这里介绍一种比较巧妙的思路 —— 基于位图。

假设原有元素 n 个,则最终组合结果是 2n−1 个。我们可以用位操作方法:假设元素原本有:a,b,c 三个,则 1 表示取该元素,0 表示不取。故取a则是001,取ab则是011。所以一共三位,每个位上有两个选择 0 和 1。而000没有意义,所以是2n−1个结果。

这些结果的位图值都是 1,2…2^n-1。所以从值 1 到值 2n−1 依次输出结果:

001,010,011,100,101,110,111 。对应输出组合结果为:a,b,ab,c,ac,bc,abc
因此可以循环 1~2^n-1,然后输出对应代表的组合即可。有代码如下:

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

void Combination(char *str)
{
    if(str == NULL)
        return ;
    int len = strlen(str);
    int n = 1<<len;
    for(int i=1;i<n;i++)    //从 1 循环到 2^len -1
    {
        for(int j=0;j<len;j++)
        {
            int temp = i;
            if(temp & (1<<j))   //对应位上为1,则输出对应的字符
            {
                printf("%c",*(str+j));
            }
        }
        printf("\n");
    }
}

void main()
{
    char str[] = "abc";
    Combination(str);
}

非递归

由于非递归的方法是基于对元素大小关系进行比较而实现的,所以这里暂时不考虑存在相同数据的情况。

在没有相同元素的情况下,任何不同顺序的序列都不可能相同。不同的序列就一定会有大有小。也就是说,我们只要对序列按照一定的大小关系,找到某一个序列的下一个序列。那从最小的一个序列找起,直到找到最大的序列为止,那么就算找到了所有的元素了。

好了,现在整体思路是清晰了。可是,要怎么找到这里说的下一个序列呢?这个下一个序列有什么性质呢?

T[i]下一个序列T[i+1]是在所有序列中比T[i]大,且相邻的序列。关于怎么找到这个元素,我们还是从一个例子来入手吧。

现在假设序列T[i] = {6, 4, 2, 8, 3, 1},那么我们可以通过如下两步找到它的下一个序列。

1550061912.png

看完上面的两个步骤,不知道大家有没有理解。如果不理解,那么不理解的点可能就在于替换点和被替点的寻找,以及之后为什么又要进行反转上。我们一个一个地解决问题吧。

这样,思路已经完全梳理完了,现在就是对其的实现了。只是为了防止给定的序列不是最小的,那就需要对其进行按从小到大进行排序。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void Swap(char *a, char *b)
{
    char t = *a;
    *a = *b;
    *b = t;
}
//反转区间
void Reverse(char *a, char *b)
{
    while (a < b)
        Swap(a++, b--);
}
//下一个排列
bool Next_permutation(char a[])
{
    char *pEnd = a + strlen(a);
    if (a == pEnd)
        return false;
    char *p, *q, *pFind;
    pEnd--;
    p = pEnd;
    while (p != a)
    {
        q = p;
        --p;
        if (*p < *q) //找降序的相邻2数,前一个数即替换数
        {
            //从后向前找比替换点大的第一个数
            pFind = pEnd;
            while (*pFind <= *p)
                --pFind;
            //替换
            Swap(pFind, p);
            //替换点后的数全部反转
            Reverse(q, pEnd);
            return true;
        }
    }
    Reverse(p, pEnd);//如果没有下一个排列,全部反转后返回true
    return false;
}
int QsortCmp(const void *pa, const void *pb)
{
    return *(char*)pa - *(char*)pb;
}
int main()
{
    char szTextStr[] = "abc";
    printf("%s的全排列如下:\n", szTextStr);
    //加上排序
    qsort(szTextStr, strlen(szTextStr), sizeof(szTextStr[0]), QsortCmp);
    int i = 1;
    do {
        printf("第%3d个排列\t%s\n", i++, szTextStr);
    } while (Next_permutation(szTextStr));
    return 0;
}

参考

https://blog.csdn.net/lemon_tree12138/article/details/50986990

Responses

From now on, bravely dream and run toward that dream.
陕ICP备17001447号·苏公网安备 32059002001895号