美文网首页
字符串的排列与组合问题

字符串的排列与组合问题

作者: 进击的Lancelot | 来源:发表于2018-12-20 19:38 被阅读0次

排列问题

问题描述:已知字符串的中字符是互不相同的,求所有可能的字符排列。例如输入序列ab,则得到的所有可能序列应当为aa、ab、ba、bb

思路:此题目可以采用递归的思想,由于所有可能排列的位数均是n位,可以利用一个长度为n的数组array[]来存放最终要输出的结果,并以array_pos表示数组中存放的字符下标,当array_pos==len时,输出array的值。由于含有n个字符的字符串,满足条件的排列共有n^n个,因此在递归当中需要用到一个for循环。

设f(str,array,len,pos)为输出可能的排列序列的函数,则递归模型如下:
终止条件:f(str,array,len,pos) ≡ {输出符合条件的排列;return}  若len==array_pos
递归主体:f(str,array,len,pos) ≡ {将str中对应的字符暂存到array中;
                                 f(str,array,len,pos+1)}   若len ≠ array_pos
#include <iostream>
using namespace std;
void Permutation(const char *str,char array[],int len, int array_pos) {
    if (len == array_pos) {
        for (int i = 0; i < len; i++)
            cout << array[i];
        cout << endl;
        return;
    }
    for (int j = 0; j < len; j++) {
        array[array_pos] = str[j];
        Permutation(str, array, len, array_pos+1);
    }
}
int main()
{
    const char* str = "abc";
    char* array = new char[3];
    int length = strlen(str);
    Permutation(str, array, length, 0);
    return 0;
}

时间复杂度:O(n^n),空间复杂度:O(n)

组合问题

问题描述:已知字符串中的字符是互不相同的,编写程序输出字符串的任意组合,例如给定abc,则任意组合为a、b、c、ab、ac、bc、abc

解法一:此题目可以采用递归的方式进行处理,对于n个字符中,取m个字符的排列,可分为如下两种情况
情况①:将第1个元素保留,并在剩余的n-1个元素中选取m-1个元素进行组合
情况②:跳过第1个元素,在剩余的n-1个元素中选取m个元素进行组合

设f(str,buf,num)为输出任意组合的函数,则递归模型如下:
终止条件:f(str,buf,num) ≡ {输出buf;return}
            若num==0【在n个元素中,能够找到符合条件的m个字符组成的组合】
         f(str,buf,num) ≡ {不做任何事情,直接return}
            若*str=='\0'【在n个元素中,找不到符合条件的m个字符组成的组合】
递归主体:f(str,buf,num) ≡ {将str中的字符暂存至buf中;
                                f(str+1,buf,num-1)}   对应情形1
         f(str,buf,num) ≡ {将buf中的字符删除;
                                f(str+1,buf,num)} 对应情形2
#include <iostream>
#include <vector>
using namespace std;
void output(vector<char> buffer) {
    for (vector<char>::iterator iter = buffer.begin(); iter != buffer.end(); iter++)
        cout << *iter;
    cout << endl;
}
void Combination(const char* str,vector<char> &buffer,int num) {
    if (num == 0) {
        output(buffer);
        return;
    }
    if (*str == '\0')
        return;
    buffer.push_back(*str);
    Combination(str + 1, buffer, num - 1);
    buffer.pop_back();
    Combination(str + 1, buffer, num);
}
int main(){
    vector<char> buffer;
    char str[] = "abc";
    int length = sizeof(str) / sizeof(char);
    for (int i = 1; i < length; i++)
        Combination(str, buffer, i);
    return 0;
}

解法二:利用位运算
对于n个字符的字符串,其可能的组合有2^n-1种,以abc为例,则利用二进制进行表示,用1表示字符输出,0表示字符不被输出,则所有可能的结果均可表示为a(100)、b(010)、c(001)、ab(110)、ac(101)、bc(011)、abc(111)

#include <iostream>
using namespace std;
void Combination(const char* str,int len) {
    for (int i = 1; i < (1 << len); i++) {    //1<<len相当于得到2^n,实现从1~2^n-1的遍历
        for (int j = 0; j < len; j++)
            if (i & (1 << j))         //将对应为为1的字符输出
                cout << str[j];
        cout << endl;
    }
}
int main()
{
    const char str[] = "abcd";
    int len = strlen(str);
    Combination(str,len);
    return 0;
}

参考资料:《编程之法—面试和算法心得》习题

相关文章

  • 有重复字符串的排列组合(golang)

    原题:有重复字符串的排列组合 与无重复字符串的排列组合(golang)类似,只是由于golang没有set,需要把...

  • 字符串的排列与组合问题

    排列问题 问题描述:已知字符串的中字符是互不相同的,求所有可能的字符排列。例如输入序列ab,则得到的所有可能序列应...

  • 第7节:行程、排列组合问题

    1、行程问题 2、排列组合 排列 组合 分类问题,加法 分步问题,乘法

  • 字符串全排列

    经常会遇到字符串全排列的问题。例如:输入为{‘a’,’b’,’c’},则其全排列组合为abc,acb,bac,bc...

  • 字符串组合与排列

    首先我们区分一下排列和组合: 输入一个字符串,得到这个字符串的所有组合(不是排列):比如输入abc,得到a,ab,...

  • 面试题 08.08. 有重复字符串的排列组合

    题目描述: 有重复字符串的排列组合。编写一种方法,计算某字符串的所有排列组合。 示例1: 输入:S = "qqe"...

  • 无重复字符串的排列组合(golang)

    原题:无重复字符串的排列组合关联:有重复字符串的排列组合(golang) 方法一:递归 假设已经得到了除了当前字符...

  • 面试题 08.07. 无重复字符串的排列组合

    无重复字符串的排列组合。编写一种方法,计算某字符串的所有排列组合,字符串每个字符均不相同。 示例1: 示例2: 提...

  • Swift-字符串排列

    题目:确定某字符串的全部排列组合. 核心代码: 测试代码:

  • 搭配儿歌

    搭配问题有方法,区别排列与组合,顺序有关是排列,使用列表来解决。顺序无关是组合,使用连线来解决。如果名称很麻烦,编...

网友评论

      本文标题:字符串的排列与组合问题

      本文链接:https://www.haomeiwen.com/subject/pbjukqtx.html