[UVa] 10063 - Knuth's Permutation

題目網址: http://goo.gl/E2CTSE

題意: 將一長度不超過10的字串，目標字串起始為空，從原字串中第一個字元開始插入到目標字串中，假設目標字串為 C1C2...Cn，而當前需插入字元為X，則插入的方法有 XC1C2...Cn, C1XC2...Cn, C1C2X...Cn, ..., C1C2...XCn, C1C2...CnX，依序 n+1 種方法，當全部字元都插入目標字串後就是ㄧ組結果排序，求依序輸出所有結果排序。


解法: 遞迴找解。

TAG: DFS

注意:

程式碼:

	/**
	* Tittle: 10063 - Knuth's Permutation
	* Author: Cheng-Shih, Wong
	* Date: 2015/03/14
	* File: 10063 - Knuths Permuation.cpp - solve it
	*/
	// include files
	#include <iostream>
	#include <cstdio>
	#include <cstring>
	#include <string>
	using namespace std;
	// definitions
	#define FOR(i,a,b) for( int i=(a),_n=(b); i<=_n; ++i )
	#define clr(x,v) memset( x, v, sizeof(x) )
	// declarations
	string str;
	// functions
	void dfs( const string &s, const int l )
	{
	if( l == str.size() ) cout << s << endl;
	else {
	FOR( i, 0, s.size() )
	dfs( s.substr(0,i)+str[l]+s.substr(i), l+1 );
	}
	}
	// main function
	int main( void )
	{
	bool nl = false;
	// input
	while( cin >> str ) {
	// solve & output
	if( nl ) putchar('\n');
	else nl = true;
	dfs( "", 0 );
	}
	return 0;
	}

view raw 10063 - Knuth's Permutation.cpp hosted with ❤ by GitHub