欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

mooc程序设计与算法(二)003:全排列

程序员文章站 2022-05-08 19:06:26
...

003:全排列


题目链接:http://cxsjsxmooc.openjudge.cn/2020t2springall/003/

思路

  • n个字符的全排列 = 最左边元素 + (n-1)个元素的全排列
  • 当元素只有一个,最左边元素的下标为n-1(下标0开始,也就是最左边元素为最后一个元素),输出s,结束
  • 最左边元素要变化,依次和后面的元素交换,可以用到swap内置函数
  • 扩展到第i个元素开始的全排列,就是第i个元素依次和它自己以及后面的元素交换,第i个元素以及它后面的元素个数为n
  • 注意:不能以i==len-2为边界条件(len就是string的长度,最后一个元素的下标是len-1),这样的话,还剩下两个元素,也要全排列
  • 因此,以i==len-1为边界条件,也就是string的最后一个元素(0开始)
  • string和数组名不同,作为函数形参,实际上开辟了新的内存,在函数中,是对string的拷贝进行操作,每次swap之后,不用换回来
#include <iostream>
using namespace std;

void myFunc(string s, int i) {
    int len = s.length();
    if (i == len-1) {
        cout << s << endl;
        return;
    }
    for (int j = i; j < len; j++) { 
        swap(s[i], s[j]);
        myFunc(s, i + 1);

    }
    return;
}

int main() {
    string s;
    cin >> s;
    myFunc(s, 0);
}