面试题38：字符串的排列（字典序全排列）

1.求数字的全排列，允许有重复数字

http://www.cnblogs.com/cxjchen/p/3932949.html

#include<iostream>
#include <vector>
#include <stdio.h>
using namespace std;

/*
开始选定第一个元素，将后面的元素进行全排列；
接下来用后面的每个元素与第一个元素交换，并排列后面的元素
*/
static int Count = 0;

//交换begin与其后的behind的字符
void swap(vector<int>& numbers, int begin,int behind)
{
    int temp = numbers[begin];
    numbers[begin] = numbers[behind];
    numbers[behind] = temp;
}

//判断从子串的第一个字符开始，直到behind-1位置，看是否有与将要交换的behing重复的字符
bool is_swap(vector<int>& numbers, int begin,int behind)
{
    for (int i = begin; i < behind ; i++)
    {
        if (numbers[i] == numbers[behind])
        {
            return false;
        }
    }
    return true;
}

void print_numbers(vector<int> &numbers)
{
    for (int i = 0; i < numbers.size(); i++)
    {
        cout << numbers[i] << " ";
    }
    cout << endl;
}

//对于序列numbers，从begin处开始进行全排列
void full_permutation(vector<int>& numbers,int begin)
{
    //若全排列已经走到最后一个了，就不用继续下去了,输出当前字符串并计数
    if (begin == numbers.size() - 1)
    {
        print_numbers(numbers);
        Count++;
        return;
    }
    //将begin与其后的各个数字交换并进行全排列
    else
    {
        for (int i = begin; i < numbers.size(); i++)
        {
            /* 
            判断其后是否有与之前交换过的重复的数字
            若相同，则将待交换数字后移；
            若不同，则将begin与i进行交换，并以begin后一位为起点重新进行全排列
            且因为i不是最后一位，所以还得将begin与i再交换一次，继续以begin为起点向后交换直到交换到最后一位,begin才能后移
            如：12345.
            1与2交换变为21345,之后以21345为序从2开头进行递归全排列。但1还得继续与3,4,5分别交换，以32145,42315,52341进行全排列。
            */
            if (is_swap(numbers, begin, i))
            {
                swap(numbers, begin, i);
                full_permutation(numbers, begin + 1);
                swap(numbers, begin, i);
            }
        }
    }
}
int main()
{
    vector<int> numbers = { 1,2,3,3 };
    full_permutation(numbers, 0);
    cout << Count << endl;
    return 0;
}

2.牛客上的题：
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则按字典序打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

思路与上面一样，我错了好多回。在使用一个其他函数的非全局变量时，没有加上引用符号，这样那个局部变量还是普通局部变量，随函数生命周期结束而结束。

另外，由于题目要求要按字典序排列，所以最后在打印之前将result数组用sort函数排列。

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

/*
思路：选定第一个字符，对剩下的字符进行全排列；
分别将第一个字符与剩下所有字符一一交换，并求全排列
步骤：
1.求现有数组的全排列
2.将数组的第一个数与其后的每个数交换，交换过程中判断被交换的后面的数是否与前面的数重复了，若重复跳过；
3.交换后求数组的全排列
*/

vector<string> result;
static int Count = 0;

//交换数组中指定位置的两个元素
void swap(string& str, int before, int behind)
{
    char temp = str[before];
    str[before] = str[behind];
    str[behind] = temp;
}

//为了去除重复，判断待交换的后面一个数behind是否已经在前面出现过，若重复，返回false表示不能交换
bool is_swap(string& str, int begin, int behind)
{
    for (int i = begin; i < behind; i++)
    {
        if (str[i] == str[behind])
        {
            return false;
        }
    }
    return true;
}

//字典序全排列:从begin处开始
void Permutation(string& str, int begin)
{
    //若begin已经到末尾，表示一次全排列结束，输出序列并返回
    if (begin == str.length())
    {
        result.push_back(str); 
        sort(result.begin(), result.end());
        Count++;
        return;
    }
    else
    {
        //将第一位与其后每一位交换，并全排列
        for (int i = begin; str[i] != '\0'; i++)
        {
            if (is_swap(str, begin, i))
            {
                //第一次循环时，i=begin,相当于输出原序列。剩下的循环就是begin位与其后数据交换
                swap(str, begin, i);
                //交换后的数据进行全排列
                Permutation(str, begin + 1);
                //由于begin还得与每一位i进行交换，全排列，所以还是得将begin于i交换回来，继续以begin为起点交换i后面的字符
                swap(str, begin, i);
            }
        }
    }

}

//字典序全排列
vector<string> Permutation(string str) {
    if (str.empty())
        return result;
    //sort(str.begin(), str.end());
    Permutation(str, 0);
    return result;
}

int main()
{
    string str = "abc";
    result = Permutation(str);
    cout << Count << endl;
    for (int i = 0; i < result.size(); i++)
    {
        cout << result[i] << endl;
    }    
    return 0;
}