剣指offer-面接問題28:文字列の並び

タイトル:文字列を入力し、その文字列にすべての配列を入れる文字を印刷します.例えば文字列abcを入力すると、文字a、b、cが並べられるすべての文字列abc、acb、bac、bca、cab、cbaが印刷される.
構想:全配列の問題は実際には交換問題である.問題を2つの部分、最初の文字と後ろの部分に分けているので、この問題は2つのステップに分けられます:(1)最初の文字のすべての可能性を考慮して、最初の文字と後ろのすべての文字を交換します;(2)最初の文字の後ろの全体的な部分を考慮すると、この部分はまた2つの部分に分けられ、前のコードを再帰的に呼び出すことができる.
非再帰アルゴリズムを参照:http://blog.csdn.net/moses1213/article/details/51058053

void Permutation(char* pStr)
{
    if(pStr == NULL)
        return;
        
    Permutation(pStr, pStr)
}

Permutation(char* pStr, char* pBegin)
{
    if(*pBegin == '\0')
        cout << pStr << endl;
    else
    {   
        for(char* pCh = pBegin; *pCh != '\0'; ++pCh)
        {
            char temp = *pCh;
            *pCh = *pBegin;
            *pBegin = temp;
            
            Permutation(pStr, pBegin + 1);
            
            temp = *pCh;
            *pCh = *pBegin;
            *pBegin = temp;
        }
    }
}

上記のアルゴリズムは、重複入力がない場合にのみ適用され、例えば「abb」は6つの結果を出力し、そのうち重複があり、正しい結果は(3!)/(2!) = 3種類、3!3の階乗を表す.次の新しいアルゴリズムを採用します:繰り返し交換を避けるために、頭文字と交換した文字が交換されたかどうかをチェックするたびに、判断の過程は頭ポインタから現在の交換文字のポインタまで遍歴して、指す値が等しい場合、現在の文字が頭文字と交換されたことを代表して、直接現在の文字をスキップします.例えば「abb」は、aが2番目のbと交換された後に「bab」となり、aが3番目のbと交換されたときにbが1つ前にあったため、この場合は直接次のステップにジャンプする.

//     
bool HasBeSwaped(char* pBegin, char* pCurrent)
{
    for(char* pCh = pBegin; pCh != pCurrent; ++pCh)
    {
        if(*pCh == *pCurrent)
            return true;
    }
    
    return false;
}

void Permutation(char* pStr, char* pBegin)
{
    if(*pBegin == '\0')
        cout << pStr << endl;
    else
    {   
        for(char* pCh = pBegin; *pCh != '\0'; ++pCh)
        {
            if(HasBeSwaped(pBegin, pCh)
                continue;
                
            char temp = *pCh;
            *pCh = *pBegin;
            *pBegin = temp;
            
            Permutation(pStr, pBegin + 1);
            
            temp = *pCh;
            *pCh = *pBegin;
            *pBegin = temp;
        }
    }
}

void Permutation(char* pStr)
{
    if(pStr == NULL)
        return;
        
    Permutation(pStr, pStr);
}

問題の拡張:文字の組合せの問題
3つの文字a、b、cを入力すると、それらの組み合わせはa、b、c、ab、ac、bc、abcである.n文字を入力すると、このn文字は、長さが1の組合せ、長さが2の組合せ、・・・、長さがnの組合せを構成することができる.n文字の長さm(1<=m<=n)の組み合わせを求めるとき、このn文字を2つの部分に分けます.最初の文字と残りのすべての文字です.組合せに最初の文字が含まれている場合は、次のステップで残りの文字にm-1文字を選択します.組合せに最初の文字が含まれていない場合は、次のステップで残りのn-1文字からm文字を選択します.すなわち,n文字の組成長さmの組合せを求める問題を,n−1文字列の長さm−1の組合せと,n−1文字の長さmの組合せをそれぞれ求める2つのサブ問題に分解することができる.この2つのサブ問題はいずれも再帰的に解決できる.
コード実装:

void Combination(char* pStr, size_t size, vector<char> result)
{
	if(strlen(pStr) < size || size < 0)
		return;
	//        ，  
    if(size == 0)
    {
        for(auto it = result.cbegin(); it != result.cend(); ++it)
            cout << *it;
		cout << endl;
		return;
    }
	//          
    result.push_back(*pStr);
	Combination(pStr + 1, size - 1, result);

	//           
    result.pop_back();
    Combination(pStr + 1, size, result);
}

void Combination(char* pStr)
{
    if(pStr == NULL)
        return;
    for(size_t size = 1; size <= strlen(pStr); ++size)
	{
		vector<char> result;
        Combination(pStr, size, result);
	}
}

 
 八皇后问题： 
  
 
8皇后问题也可以用全排列的方式解决。问题是这样的：在8*8的国际象棋上摆放8个皇后，使其不能相互攻击，即任意两个皇后不得处在同一行、同一列或者同一对角线上。求一共有多少种符合条件的八法。
 
 
由于8个皇后任意两个不能处在同一行，那么肯定每个皇后占据一行。于是我们可以定义一个数组ColumnIndex[8]，数组中第i个数字表示位于第i行皇后的列号。先把数组ColumnIndex的8个数字分别用0~7初始化，接下来就是对数组ColumnIndex做全排列。因为我们是用不同的数字初始化数组，所以任意连个皇后肯定不同列。只需要判断每一个排列对应的8个皇后是不是在同一对角线上，也就是对于数组的两个下标i和j，是不是i-j==ColumnIndex[i] - ColumnIndex[j]或者j-i=ColumnIndex[i] - ColumnIndex[j]。
 
  
 
#include <iostream>
using namespace std;

bool IsRightArrange(int* ColumnIndex, int n)
{
	for(int i = 0; i < n; ++i)
	{
		for(int j = i+1; j < n; ++j)
		{
			if(i - j == ColumnIndex[i] - ColumnIndex[j] || j - i == ColumnIndex[i] - ColumnIndex[j])
				return false;
		}
	}

	return true;
}

void Permutation(int* ColumnIndex, int* pBegin, int& count)
{
	if(pBegin - ColumnIndex == 8)
	{
		if(IsRightArrange(ColumnIndex, 8))
			++count;
	}
	else
	{
		for(int* pSwap = pBegin; pSwap != ColumnIndex + 8; ++pSwap)
		{
			int temp = *pBegin;
			*pBegin = *pSwap;
			*pSwap = temp;

			Permutation(ColumnIndex, pBegin + 1, count);

			temp = *pBegin;
			*pBegin = *pSwap;
			*pSwap = temp;
		}
	}
}

int Queen8()
{
	int ColumnIndex[8];
	for(int i = 0; i < 8; ++i)
		ColumnIndex[i] = i;
	
	int count = 0;
	Permutation(ColumnIndex, ColumnIndex, count);

	return count;
}

int main()
{
	cout << Queen8() << endl;
	getchar();

	return 0;
}