学步园

用1、2、2、3、4、5这六个数字，写一个main函数，打印出所有不同的排列，

如：512234、412325等，要求："4"不能在第三位，"3"与"5"不能相连。

// str: 字符串
// begin: 字符串第一个字符的索引
// end: 字符串最后一个字符的索引
// cnt: 统计全排列的数目，调用之前赋值为0
void string_full_permutation_containing_duplicate_char(char *str, int begin, int end, int &cnt)
{
    if (begin >= end)
    {
        if ( strstr(str, "35") != NULL || strstr(str, "53") != NULL)
            return;
        std::cout << str << std::endl;
        ++cnt;
        return;
    }
    if (begin > 2 && str[2] == '4')
        return;
    
    string_full_permutation_containing_duplicate_char(str, begin+1, end, cnt);
    int i = begin + 1;
    while (i <= end)
    {
        if (str[begin] != str[i])
        {
            std::swap(str[begin], str[i]);
            string_full_permutation_containing_duplicate_char(str, begin+1, end, cnt);
            std::swap(str[begin], str[i]);

            while (str[i] == str[i+1])
                ++i;
        }
        ++i;
    }
}

int main(int argc, char **argv)
{
    char str[] = "122345";
    int len = strlen(str);
    int cnt = 0;
    string_full_permutation_containing_duplicate_char(str, 0, len-1, cnt);
    cout << endl << endl << cnt << endl;
}

算出的cnt=198