TopCoder SRM 575, Division 2, Level 1 : TheSwapsDivTwo

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=12499&rd=15495

概要

整数列が与えられる。
ランダムに二つの異なるインデックスを選んで、その二つの数字を交換する操作を一回する。
作られる数列の総数を求めよ。

解法

実際に交換後の数列を生成して、その総数を数えます。
集合（ C++ では set ）を用いることで重複なく数えられます。

コード

typedef vector<int> VI;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )

class TheSwapsDivTwo
{
public:
	int find( vector <int> sequence )
	{
		const int N = sequence.size();
		set<VI> res;
		
		REP( i, 0, N )
		{
			REP( j, i + 1, N )
			{
				VI tmp( sequence );
				swap( tmp[i], tmp[j] );
				res.insert( tmp );
			}
		}
		return res.size();
	}
};