学步园

偶然在网上看到一道面试题，细看下才发现是曾经被面试过的全排列问题。
于是手痒，想以OOD的思想重新实现一番。
实现可复用软件的一个重要原则是：封装变化。是故，看下全排列代码中哪些因素是不稳定的：
 1.  元素的数据类型。元素的类型可能是int, double, char等基本数据类型，不过，大部分情况下应该是用户自定义的类型。
 2.  元素的存储方式。

 3.  找到一个新排列后，如何处理一个新的排列。比如，可以直接打印输出

/// IPermArray接口封装数据的存储方式和数据类型，假设所有的元素都可以通过下标来访问。
struct IPermArray
{
	typedef unsigned int uint;
	virtual ~IPermArray() {}
	virtual uint getLength()const = 0;
	virtual bool isEqual(uint index, uint otherIndex) const = 0;
	virtual void swap(uint index, uint otherIndex) = 0;
};
/// IPermProcess接口封装对新排列的处理。
struct IPermProcess
{
	virtual ~IPermProcess(){}
	virtual void run() = 0;
};

/// Permu类依赖IPermArray和IPermProcess接口来实现全排列
class Permu{
private:
	std::shared_ptr<IPermProcess> _process;
	std::shared_ptr<IPermArray> _arr;
public:
	void setPermArray(std::shared_ptr<IPermArray> arr)
	{
		_arr = arr;
	}
	void setPermProcess(std::shared_ptr<IPermProcess> proc)
	{
		_process = proc;
	}
	void start()
	{
		if(_arr){
			return run(0, _arr->getLength());
		}
	}

private:
	typedef IPermArray::uint uint;
	void run(uint startIndex, uint endIndex){
		if(startIndex >= endIndex){
			if(_process){
				_process->run();
			}
		}

		for(uint i(startIndex); i < endIndex; ++i)
		{
			if(isAlreadySelected(i, startIndex))
			{
				continue;
			}
			_arr->swap(startIndex, i);
			run(startIndex + 1, endIndex);
			_arr->swap(startIndex, i);
		}
	}

	bool isAlreadySelected(uint curIndex, uint startIndex)
	{
		while(startIndex < curIndex)
		{
			if(_arr->isEqual(startIndex, curIndex)){
				return true;
			}
			++startIndex;
		}
		return false;
	}

};

另外再实现个通用的PermArray，用来处理普通的数据，比如Int，double，float，和char等。

template<typename T>
class GenericArray: public IPermArray, public IPermProcess
{

public:
	typedef T ElemType;
	GenericArray(ElemType* arr, uint len): _arr(arr), _len(len){}

	///IPermArray
	virtual uint getLength() const
	{
		return _len;
	}
	virtual bool isEqual(uint index, uint otherIndex) const
	{
		if(index >= _len || otherIndex >= _len)
		{
			return false;
		}
		if(index == otherIndex)
		{
			return true;
		}
		return _arr[index] == _arr[otherIndex];
	}
	virtual void swap(uint index, uint otherIndex)
	{
		if(index >= _len || otherIndex >= _len)
		{
			return;
		}
		if(index == otherIndex)
		{
			return;
		}
		if(_arr[index] == _arr[otherIndex])
		{
			return;
		}
		ElemType tmp(_arr[index]);
		_arr[index] = _arr[otherIndex];
		_arr[otherIndex] = tmp;
	}

	///IPermProcess
	virtual void run(){
		for(uint i(0); i < _len - 1; ++i)
		{
			std::cout << _arr[i]<< ", ";
		}
		std::cout << _arr[_len - 1] << std::endl;
	}
private:
	ElemType* _arr;
	uint _len;
};

最后是测试代码

int main() {
	int iarr[4] = {1, 2, 3, 3};
	typedef GenericArray<int> IntArray;
	std::shared_ptr<IntArray> intArr(new IntArray(iarr, sizeof(iarr)/sizeof(iarr[0])));

	typedef GenericArray<char> CharArray;
	char carr[4] = {'a', 'b', 'c', 'a'};
	std::shared_ptr<CharArray> chArr(new CharArray(carr, sizeof(carr)/sizeof(carr[0])));

	Permu permuGenerator;
//	permuGenerator.setPermArray(intArr);
//	permuGenerator.setPermProcess(intArr);

	permuGenerator.setPermArray(chArr);
	permuGenerator.setPermProcess(chArr);

	permuGenerator.start();
	return 0;
}

对于其他的数据，比如STL的vectory，list等只要实现了IPermArray，和IPermProcess接口可以采用Permu来处理全排列了。当然，它们也可能内置了全排列的算法。