最近心血来潮,想自己写个求解排列组合的小东西。以2个数组为例: arr1 = {'a', 'b', 'c'}; arr2={'1', '2'}; ,将数组中元素的所有排列组合枚举出来:a1 , a2, b1, b2, c1, c2, 1a, 1b.............。这里仅仅是个例子,需要解决的问题域是:数组个数是不定的,数组元素个数也是不定的。 先将问题分解,排列组合嘛,先求排列(数组位置)再对每一种排列求组合。
求排列
如果有n个数组,那么排列数为n!,这里需要将这些排列都枚举出来。我的解法如下:
假设有序列012那么,它的排列依次为012,102,120,210,201,021。不难发现规律,就是不断的将第一个元素向后移动,每一步都能得到一个排列,这个循环结束的条件就是:如果得出的排列与第一个排列相等,那么结束循环。
1 #pragma once
2 #include <vector>
3 #include <string>
4 #include <algorithm>
5
6 typedef std::vector<size_t> size_t_vector;
7 typedef std::vector<std::string> result_vector; ///< 存放排列组合的结果
8
9 /**
10 *class permutation
11 *@brief 求排列
12 *
13 *@see
14 *@author fubingheng
15 *@date 2012-05-10
16 */
17 class permutation
18 {
19 public:
20 typedef std::vector<size_t_vector> permutation_vector;
21
22 /**
23 *@brief 比较两个vector是否相等
24 */
25 template< typename T>
26 static bool compare_vector(const std::vector<T> &a, const std::vector<T> &b)
27 {
28 if (a.size() != b.size())
29 {
30 return false;
31 }
32
33 for (size_t i = 0; i < a.size(); ++i)
34 {
35 if (a[i] != b[i])
36 {
37 return false;
38 }
39 }
40
41 return true;
42 }
43
44
45 permutation(size_t n)
46 {
47 //求n的排列数
48 if (n == 0)
49 {
50 throw std::exception("can't 0");
51 }
52
53 //构造第一个排列
54 size_t_vector first;
55 for (size_t i = 0; i < n; ++i)
56 {
57 first.push_back(i);
58 }
59 permutations_.push_back(first);
60
61 size_t_vector next = first;
62 size_t_vector::iterator pos = next.begin();
63 while (1)
64 {
65 size_t_vector::iterator temppos = pos++;
66 if (pos != next.end())
67 {
68 //元素移动一个位置,得到新的排列
69 std::swap(*temppos, *pos);
70 if (compare_vector(first, next))
71 {
72 break;
73 }
74 //如果排列是有效的(和第一个不相等),放入容器中(拷贝构造)
75 permutations_.push_back(next);
76 }
77 else
78 {
79 //移动到末尾了,从头再来
80 pos = next.begin();
81 }
82 }
83 }
84
85 permutation::permutation_vector get_permutation_vector(){return permutations_;}
86 private:
87 permutation_vector permutations_; ///< 存放枚举的排列
88 };
求组合
通过排列已经能够确定数组的位置了。假设arr1在位置0,arr2在位置1的排列,那么求这个排列下的出所有组合数。
1 std::string str;
2 for (int i = 0; i < arr1_size; ++i)
3 {
4 str = "";
5 str += arr1[i]; //确定第一个元素
6 for(int j = 0; j < arr2_size; ++j)
7 {
8 str += arr1[j];
9 std::cout<<" "<<str;
10 }
11 }
如果再有个数组arr3在位置2,那么只能在最后一个for里面再嵌入一个for了,依次类推.........。而数组个数恰恰是动态变化的,所以不能如此“硬编码”,那么还有什么动态的方法么。等等看见这样的情形是不是立刻让人想到了递归?恩,是的递归,还有模板元。的确,递归能解决这个问题,而且也比较容易写出(最接近一般的思路),这里就不实现了。但大家都知道,递归通常只能有17层。记得读书的时候,课本上说过,所有递归的方式都能用非递归替代。这里先不管是否有必要用非递归的方式实现,只是个人兴趣而已。这里不难发现,难点是for的嵌套层级是由数组数组个数n决定的,而且不能硬编码至程序中。那么我们只能换一种思路。根据数学知识,我们知道,排列数y =arr1_sizearr2_size..........等号的右边是不是正好对应了上面伪码的嵌套结构?每个嵌套for正好循环一个数组长度,那我们从等号左边思考会如何?
for (int i = 0; i < y; ++i)
{
...............
}
用一个总的循环降解了嵌套循环的结构。但新的问题也来了,那就是元素的确定问题。你怎么确定每个位置的元素?这个问题让我想了好久。设有0~n个数组,数组对应的元素个数为S0~Sn,也就是数组具有下面这种形式
arr0 = {x0, x1, x2........xn} (Xn为元素下标) size = S0。
组合数为y, f为某种函数关系:那么Y和X
Y0 = f(arr0.x0, arr1.x0, arr2.x0,.........arrn-1.x0, arrn.x0)
Y1 = f(arr0.x0, arr1.x0, arr2.x0,.........arrn-1.x0, arrn.x1)
Y2 = f(arr0.x0, arr1.x0, arr2.x0,.........arrn-1.x0, arrn.xn)
...............................................................
Yn = f(arr0.x0, arr1.x0, arr2.x0,.........arrn-1.x0, arrn.xn)
Yn+1 = f(arr0.x0, arr1.x0, arr2.x0,........., arrn-1.x1, arrn.x0)
看到规律了么?对,从最后一个数组arrn的下标不断加1,当arrn加到最后一位时(加了Sn次,因为这个数组的大小为Sn),向前它一个数组(arrn-1)进1。接着继续从最后一个数组取,取到Xn后,再向arrn-1进1。由于最后一位arrn不断的向arrn-1进位(每加Sn次进一位),所以arrn-1会加到arrn-1.Xn(也就是arrn-1的大小Sn-1),这时arrn-1会向arrn-2进1,同时arrn-1.Xn会复位回arrn-1.X0,依次反复直到arr0.Xn为止。记住,每次加1都是最后一个坐标。这种加1以后要进行y =arr1_sizearr2_size..........次。
1 class coordinate
2 {
3 public:
4 //构造函数
5 coordinate(const size_t_vector & array_size_vecotor)
6 :array_sizes_(array_size_vecotor)
7 {
8 if(array_size_vecotor.empty())
9 {
10 throw std::exception("can't empty vector");
11 }
12
13 for (size_t i = 0; i < array_size_vecotor.size(); ++i)
14 {
15 coordinates_.push_back(0);
16 }
17 }
18 //拷贝构造
19 coordinate(const coordinate & other)
20 {
21 if (this != &other)
22 {
23 this->coordinates_ = other.coordinates_;
24 this->array_sizes_ = other.array_sizes_;
25 }
26 }
27 //赋值
28 coordinate & operator = (const coordinate & other)
29 {
30 if (this != &other)
31 {
32 this->coordinates_ = other.coordinates_;
33 this->array_sizes_ = other.array_sizes_;
34 }
35
36 return *this;
37 }
38
39 //前++
40 coordinate & operator ++ ()
41 {
42 size_t pos = array_sizes_.size() - 1;//最后一个坐标
43 do
44 {
45 size_t temp = coordinates_[pos];
46 ++temp;//最后一个坐标加1
47
48 if (temp == array_sizes_[pos]) // 判断加1后是否应该进位
49 {
50 //应该进位
51 coordinates_[pos] = 0;
52 coordinates_[pos - 1] = coordinates_[pos - 1] + 1;
53 }
54 else
55 {
56 //不进位
57 coordinates_[pos] = temp;
58 break;
59 }
60 --pos;
61 } while (pos > 0);
62
63 return *this;
64 }
65 //后++
66 const coordinate operator ++ (int)
67 {
68 coordinate t(*this);
69 size_t pos = array_sizes_.size() - 1;
70 do
71 {
72 size_t temp = coordinates_[pos];
73 ++temp;
74
75 if (temp == array_sizes_[pos])
76 {
77 coordinates_[pos] = 0;
78 //coordinates_[pos_ - 1] = coordinates_[pos_ - 1] + 1;
79 }
80 else
81 {
82 coordinates_[pos] = temp;
83 break;
84 }
85 --pos;
86 } while (pos > 0);
87
88 return t;
89 }
90
91
92 size_t_vector get_coordinates() { return coordinates_;}
93 private:
94 size_t_vector coordinates_;///< 存放X0, X1.......Xn
95 size_t_vector array_sizes_;///< 存放S0,S2.......Sn
96 };
将两个模块合并
1 //求排列组合
2 template <typename T>
3 void permutation_and_combination(const std::vector<std::vector<T>> & inVal, result_vector & outVal)
4 {
5 typedef std::vector<std::vector<T>> arr_vector;
6 permutation _permutation(inVal.size());
7 permutation::permutation_vector all_permutation = _permutation.get_permutation_vector();
8
9 for (size_t i = 0; i < all_permutation.size(); ++i)
10 {
11 //对每一种排列求组合
12 size_t_vector array_size;
13 std::vector<std::vector<T> > carray;
14 for (size_t j = 0; j <all_permutation[i].size();++j)
15 {
16 array_size.push_back(inVal[all_permutation[i][j]].size());
17 carray.push_back(inVal[all_permutation[i][j]]);
18 }
19
20 coordinate _coordinate(array_size);
21 size_t total = 1;
22 std::for_each(array_size.begin(), array_size.end(), [&total](size_t_vector::value_type &val)
23 {
24 total *= val;
25 });
26
27 for (size_t i = 0; i < total; ++ i)
28 {
29 if (i != 0 )
30 {
31 ++_coordinate;
32 }
33 size_t_vector _coordinates = _coordinate.get_coordinates();
34 std::string str;
35 for (size_t j = 0; j < carray.size(); ++j)
36 {
37 str += carray[j][_coordinates[j]];
38 }
39 outVal.push_back(str);
40 }
41 }
42 }
对应的main函数
1 #include "stdafx.h"
2 #include <iostream>
3 #include "permutation_combination.h"
4 int _tmain(int argc, _TCHAR* argv[])
5 {
6 // 动态构造两个数组
7 std::vector<char> arr1;
8 arr1.push_back('a');
9 arr1.push_back('b');
10 arr1.push_back('c');
11
12 std::vector<char> arr2;
13 arr2.push_back('1');
14 arr2.push_back('2');
15
16 std::vector<std::vector<char>> inVal;
17 inVal.push_back(arr1);
18 inVal.push_back(arr2);
19 result_vector outVal;//计算结果
20 permutation_and_combination<char>(inVal, outVal);
21 return 0;
22 }
以上代码均在VS2010下编译通过。
原文链接: https://www.cnblogs.com/iq50/archive/2012/05/11/2495971.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/49986
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!