放牧代码和思想
专注自然语言处理、机器学习算法
    博主不用扣扣,公事请博客留言,私事请微博私信。开源项目一律GitHub见,发错地方恕不回复,谢谢。

实现输出泛型集合所有排列组合的泛型函数

看了一半《C++标准程序库—自修教程与参考手册》,忍不住写了个泛型函数玩玩,输出某集合里所有元素的可能的排列组合。此函数有两个版本,permutate适用于各种情况,包括集合里有相同元素的情况,但是效率和空间都不好。而permutate_unique仅适用于集合里元素unique的情况,且效率和空间很好。

#include <iostream>
#include <algorithm>
#include <iterator>
#include <deque>
#include <set>
using namespace std;

template <class T>
void permutate(const T& coll)
{
	T back(coll);
	sort(back.begin(), back.end());
	for (T::const_iterator pos = back.begin(); pos != back.end(); ++pos)
	{
		cout << *pos;
	}
	cout << endl;
	while (next_permutation(back.begin(), back.end()))
	{
		for (T::const_iterator pos = back.begin(); pos != back.end(); ++pos)
		{
			cout << *pos;
		}
		cout << endl;
	}
}

template <class T>
void permutate_unique(const T& coll)
{
	unsigned int size = coll.size();
	unsigned int* p = new unsigned int[size];
	for (int i = 0; i < size; ++i)
	{
		p[i] = i;
	}

	for (T::const_iterator pos = coll.begin(); pos != coll.end(); ++pos)
	{
		cout << *pos;
	}
	cout << endl;

	while (next_permutation(p, p + size))
	{
		for (int i = 0; i < size; ++i)
		{
			T::const_iterator pos = coll.begin();
			advance(pos, p[i]);
			cout << *pos;
		}
		cout << endl;
	}

	delete[] p;
}

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
	// test int
	set<int> coll1;
	coll1.insert(3);
	coll1.insert(1);
	coll1.insert(2);
	permutate_unique(coll1);
	cout << endl;
	// test char
	set<char> coll2;
	coll2.insert('c');
	coll2.insert('a');
	coll2.insert('b');
	permutate_unique(coll2);
	cout << endl;
	// test multi char
	// test char
	deque<char> coll3;
	coll3.push_front('a');
	coll3.push_front('a');
	coll3.push_front('b');
	permutate(coll3);
	system("pause");
	return 0;
}
///////////////////////////End Sub//////////////////////////////////

输出:

123
132
213
231
312
321

abc
acb
bac
bca
cab
cba

aab
aba
baa
请按任意键继续. . .

知识共享许可协议 知识共享署名-非商业性使用-相同方式共享码农场 » 实现输出泛型集合所有排列组合的泛型函数

分享到:更多 ()

评论 欢迎留言

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机