C++ 容器

Posted on | In , |

[TOC]

c++ STL

容器

  • 序列容器

    • vector

    • array

    • queue

    • deque

    • list

    • forward_list

  • 关联容器

    • map

    • set

    • unordered_map

    • multimap

    • unordered_multimap

    • multiset

    • unordered_multiset

1. vector

初始化

1
2
3
4
5
6
7
8
9
10
    vector<int> vec1;
    vector<float> vec2(3);
    vector<char> vec3(3,'a');
    vector<char> vec4(vec3);
    vector<vector<int>> vecNN(5);

//<1> 第一个是空的整形vector，我们没有给他添加任何元素。
//<2>第二个初始化了一个有3个元素的vector，由于并没有指定初始 值，将会使用编译器默认的初始值。
//<3>第三个初始化了含有3个a的字符vector，括号中第二个值代表着所有元素的指定值。
//<4>第四个vector通过拷贝vec3中的元素初始化vec4，它们的元素会一模一样。

push_back()

insert()

size()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <vector>
using namespace std;

vector<int> vect1,vect2;

//# push_back
vect1.push_back(1);
vect1.push_back(2);

vect2.push_back(8);
vect2.push_back(9);

//# insert
vect2.insert(vect2.end(),vect1.begin(),vect1.end());

//# size
vect2.size();

for (int i = 0; i < vect2.size(); i++)
{
    cout<<vect2[i]<<endl;
}

Delete ~ ~Erase()

  1. erase返回一个迭代器，指向被删除元素之后的位置。
  2. 如果尝试删除超出向量范围的索引，erase将抛出std::out_of_range异常。
  3. 在删除元素后，所有后续元素的索引都会减少。例如，如果你删除了索引为2的元素，索引为3的元素会变成索引为2的元素。
  4. erase会释放被删除元素占用的内存。
  5. 使用erase后，向量的长度会减少。
1
2
3
4
5
6
7
8
9
10
11
12
    std::vector<int> vec = {1, 2, 3, 4, 5};  

    // 删除索引为2的元素（即数字3）  
    vec.erase(vec.begin() + 2);  

    // 输出修改后的向量  
    for (int num : vec) {  
        std::cout << num << " ";  
    }  
    std::cout << std::endl;  

vect.erase(std::remove(vect.begin(), vect.end(), id), vect.end());

find

1
2
3
4
5
6
//# find
auto iter = find(vec2.begin(), vec2.end(), 9);
if (iter != vec2.end())
{
    cout << "Find IT!";
}

replace

1
2
std::vector<int> vec = {1, 2, 3, 4, 5};  
vec[2] = 10; // 将索引为2的元素替换为10

find + delete (删除找到的第一个元素)

1
2
3
vector<int> vec = {3, 4, 5, 6, 7, 4};
auto iter = find(vec.begin(), vec.end(), 4);
vec.erase(iter);

find + replace

1
2
3
4
5
6
std::vector<int> vec = {1, 2, 3, 4, 5};  
for (auto& num : vec) {  
    if (num == 3) {  
        num = 10; // 将值为3的元素替换为10  
    }  
}

max

1
2
3
4
vector<int> a = { 2,4,6,7,1,0,8,9,6,3,2 };
auto maxPosition = max_element(a.begin(), a.end());
cout << *maxPosition << " at the postion of " << maxPosition - a.begin() <<endl;
//cout << a[maxPosition - a.begin()] << " at the postion of " << distance(a.begin(), maxPosition) << endl;

vector TO 数组

1：memcpy
1
2
3
4
5
6
7
8
9
10
// 1 vector to arr
vector<char> vec(10, 'c'); // 10个c字符
char charray[10];
memcpy(charray, &vec[0], vec.size()*sizeof(vec[0])); // 注意数组越界--数据超长

// 2. arr to vector
// 2.1 直接赋值-init
vector<char> v(arr, arr+sizeof(arr))
// 2.2 copy    
memcpy(&vec[0], arr, sizeof(arr));

ref baidu wenku

2： std::copy vector to arr
1
2
3
4
vector<int> input({1,2,3,4,5});
int arr[input.size()];
//Copies the range [first,last) into result.
std::copy(input.begin(), input.end(), arr);

ref:: https://www.techiedelight.com/convert-vector-to-array-cpp/

max

1
2
3
vector<int> a = { 2,4,6,7,1,0,8,9,6,3,2 };
auto maxPosition = max_element(a.begin(), a.end());
cout << *maxPosition << " at the postion of " << maxPosition - a.begin() <<endl;### map

vector 切片

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 方法1
std::vector<int> vector{1,2,3,4,5,6,7,8,9};
// 截取[0,4]
std::vector<int>::const_iterator first1 = vector.begin();
std::vector<int>::const_iterator last1  = vector.begin() + 4;
std::vector<int> cut1_vector(first1, last1);


// 截取[-4,]
std::vector<int>::const_iterator first2 = vector.end() - 4;
std::vector<int>::const_iterator last2  = vector.end();
std::vector<int> cut2_vector(first2, last2);

// 方法2
vector<int> Arrs {1,2,3,4,5,6,7,8,9}; // 假设有这么个数组,要截取中间第二个元素到第四个元素：2，3，4
vector<int>::const_iterator Fist = Arrs.begin() + 1; // 找到第二个迭代器
vector<int>::const_iterator Second = Arrs.begin() + 2; // 找到第三个迭代器
vector<int> Arr2;
Arr2.assign(First,Second); //使用assign() 成员函数将Arrs对应位置的值存入Arrs2数组中

去重

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 1
vector<int> vec = {1, 2, 3, 1, 1};
set<int> s(vec.begin(), vec.end());
vec.assign(s.begin(), s.end());

// 2
vector<int> vec = {1, 2, 3, 1, 1};
sort(vec.begin(), vec.end());
vec.erase(unique(vec.begin(), vec.end()), vec.end());
// unique函数将重复的元素放到 vector 的尾部，然后返回指向第一个重复元素的迭代器


// 3 remove 删除所有的7
auto ret = std::remove(vec.begin(), vec.end(), 7);
vec.erase(ret, vec.end());
1
2


2. Map

存放的元素都是K-V键值对，并且Key是不能重复的。

构造函数

1
map<int, string> mapStudent;

插入数据

1
2
3
4
mapStudent.insert(pair<int, string>(1, "student_one"));             //pair<>()函数
mapStudent.insert(map<int, string>::value_type (1, "student_one")); //map<>::value_type
mapStudent.insert(make_pair(1, "student_one"));                     //make_pair()函数
mapStudent[1] = "student_one";                                      //数组方式

查找

1
2
3
4
5
iter = mapStudent.find(1); // find(key)
if (iter != mapStudent.end())
    cout << "Find " << iter->second ;
else
    cout << "Dont not find";

遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
map<int, CString>  maps;      // 或者map < int, 结构体名>   maps;
for (int i =0; i < maps.size(); i++)
{
     CString s=maps[ i ];
}   

map<CString, 结构体名> maps;
map<CString, 结构体名>::iterator iter;   //迭代器遍历 如vector 也可使用
for(  iter=maps.begin();     iter!=maps.end();   iter++)
{
    CString a = iter - > first;
    结构体名 p = iter - > second;
}

删除与清空元素

1
2
3
4
5
6
7
8
9
// 迭代器删除
iter = mapStudent.find("123");
mapStudent.erase(iter);

// 关键字删除
int n = mapStudent.erase("123");

// 清空map
mapStudent.erase(mapStudent.begin(), mapStudent.end())

大小

1
int mSize = mapStudent.size();

原文链接：https://blog.csdn.net/bandaoyu/article/details/87775533

3. unordered_map

存放的元素都是K-V键值对，并且Key是不能重复的。

1
2
3
4
5
#include <unordered_map>
// 如果C++的版本低于C++11,则会报错：[Error] ‘unordered_map’ was not declared in this scope
// 则需要将头文件改为
#include<tr1/unordered_map>
using namespace std::tr1;

建立Hashmap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
unordered_map<int,int> Hashmap;


// **建立迭代器**
unordered_map<int,int>::iterator it;

//插入键值对
// insert函数
Hashmap.insert(make_pair<int,int>(1,3));
Hashmap.insert(make_pair(1,3));
// 通过键添加
Hashmap[3]=1;

//其他函数
it = Hashmap.begin() //指向哈希表的第一个容器
it = Hashmap.end() //指向哈希表的最后一个容器，实则超出了哈希表的范围，为空
Hashmap.size() //返回哈希表的大小
Hashmap.empty() //判断哈希表是否为空，返回值为true/false
Hashmap.clear() //清空哈希表

// 通过key值查找键值对
it = Hashmap.find(2) //查找key为2的键值对是否存在 ,若没找到则返回Hashmap.end()
if(Hashmap.find(2)!=Hashmap.end()) //判断找到了key为2的键值对

//通过key值查找该key值下的键值对对数
Hashmap.count(1) //返回 1


//swap交换两个Hashmap的键值对
Hashmap1.swap(Hashmap2);
swap(Hashmap1,Hashmap2);

遍历Map

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
//第一种
unordered_map<int, int> Hashmap;
for (auto p : Hashmap) {
    int front = p.first;   //key
    int end = p.second;   //value
}

//第二种
unordered_map<int, int> Hashmap;
for(auto it=Hashmap.begin();it!=Hashmap.end();it++)
{
    int front = it->first;   //key
    int end = it->second;   //value
}

//第三种
unordered_map<int,int> hash;
unordered_map<int,int>::iterator it;
it = hash.begin();
while(it != hash.end())
{
    int front= it->first;   //key
    int end = it->second;   //value
    it++;
}

辨析.map VS unordered_map

内部实现机理不同
map： map内部实现了⼀个红⿊树（红⿊树是⾮严格平衡⼆叉搜索树，⽽AVL是严格平衡⼆叉搜索树），红⿊树具有⾃动排序的功能，因此map内部的所有元素都是有序的，红⿊树的每⼀个节点都代表着map的⼀个元素。因此，对于map进⾏的查找，删除，添加等⼀系列的操作都相当于是对红⿊树进⾏的操作。map中的元素是按照⼆叉搜索树（⼜名⼆叉查找树、⼆叉排序树，特点就是左⼦树上所有节点的键值都⼩于根节点的键值，右⼦树所有节点的键值都⼤于根节点的键值）存储的，使⽤中序遍历可将键值按照从⼩到⼤遍历出来。

unordered_map: 内部实现了⼀个哈希表（也叫散列表，通过把关键码值映射到Hash表中⼀个位置来访问记录，查找的时间复杂度可达到O(1)，其在海量数据处理中有着⼴泛应⽤）。因此，其元素的排列顺序是⽆序的。

map

特点
map 有序性，这是map结构最⼤的优点，其元素的有序性在很多应⽤中都会简化很多的操作
红⿊树，内部实现⼀个红⿊书使得map的很多操作在lgn的时间复杂度下就可以实现，因此效率⾮常的⾼
缺点： 空间占⽤率⾼，因为map内部实现了红⿊树，虽然提⾼了运⾏效率，但是因为每⼀个节点都需要额外保存⽗节点、孩⼦节点和红/⿊
性质，使得每⼀个节点都占⽤⼤量的空间
适⽤处：对于那些有顺序要求的问题，⽤map会更⾼效⼀些
unorder_map 优点： 因为内部实现了哈希表，因此其查找速度⾮常的快
缺点： 哈希表的建⽴⽐较耗费时间
适⽤处：对于查找问题，unordered_map会更加⾼效⼀些，因此遇到查找问题，常会考虑⼀下⽤unordered_map

总结：

内存占有率的问题就转化成红⿊树 VS hash表 , 还是unorder_map占⽤的内存要⾼。

  • 但是unordered_map执⾏效率要⽐map⾼很多
  • 对于unordered_map或unordered_set容器，其遍历顺序与创建该容器时输⼊的顺序不⼀定相同，因为遍历是按照哈希表从前往后依次遍历的

map和unordered_map的使⽤

  • unordered_map的⽤法和map是⼀样的，提供了 insert，size，count等操作，并且⾥⾯的元素也是以pair类型来存贮的。
  • 其底层实现是完全不同的，上⽅已经解释了，但是就外部使⽤来说却是⼀致的。

4. set

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
// init
std::set<int> myset{1, 2, 3, 4, 5};
// init 2
int arr[] = {1, 2, 3, 4, 5};
std::set<int> myset(arr, arr+5);

// insert
std::set<int> myset;
myset.insert(1);
myset.insert(2);


// delete
auto cnt = myset.erase(2); // 返回删除几个元素，0个，1个
// clear
myset.clear();

// for 
for (std::set<int>::iterator it = myset.begin(); it != myset.end(); it++) {
// or
// for (auto it = myset.begin(); it != myset.end(); it++) {
    std::cout << *it << " ";
}

// for 逆序
for (auto it = myset.rbegin(); it != myset.rend(); it++) {
    std::cout << *it << " ";
}

// count 元素查询
std::set<int> myset;
myset.insert(2);
myset.insert(4);
myset.insert(6);
std::cout << myset.count(4) << "\n"; // 1
std::cout << myset.count(8) << "\n"; // 0

// find 元素查询
std::set<int> myset = {2, 4, 6};
auto search = myset.find(2);
if (search != myset.end()) {
    std::cout << "Found " << *search << "\n"; // Found 2
} else {
    std::cout << "Not found\n";
}

// empty 
if (myset.empty())
    cout << "empty set " << endl;

https://shengyu7697.github.io/std-set/

排列组合

算法-递归法实现排列组合C++

通用 排列/组合 函数(c++实现)

全排列(stl)

从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。如果这组数有n个，那么全排列数为n!个。

比如a，b，c的全排列一共有3！= 6 种 分别是{a, b, c}、{a, c, b}、{b, a, c}、{b, c, a}、{c, a, b}、{c, b, a}。

api:

prev_permutation

next_permutation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <algorithm>
using namespace std;
int main ()
{
    int arr[] = {3,2,1};
    cout<<"用prev_permutation对3 2 1的全排列"<<endl;
    do
    {
        cout << arr[0] << ' ' << arr[1] << ' ' << arr[2]<<'\n';
    }
    while (prev_permutation(arr,arr+3) );      
    ///获取上一个较大字典序排列，如果3改为2，只对前两个数全排列

    int arr1[] = {1,2,3};
    cout<<"用next_permutation对1 2 3的全排列"<<endl;
    do
    {
        cout << arr1[0] << ' ' << arr1[1] << ' ' << arr1[2] <<'\n';
    }
    while (next_permutation(arr1,arr1+3) );      
    ///获取下一个较大字典序排列，如果3改为2，只对前两个数全排列

    ///注意数组顺序，必要时要对数组先进行排序

    return 0;
}
全排列递归思路

我们可以将这个排列问题画成图形表示，即排列枚举树，比如下图为{1,2,3}的排列枚举树，此树和我们这里介绍的算法完全一致；

image-20220507112024363

算法思路：

(1)n个元素的全排列=（n-1个元素的全排列）+（另一个元素作为前缀）；

(2)出口：如果只有一个元素的全排列，则说明已经排完，则输出数组；

(3)不断将每个元素放作第一个元素，然后将这个元素作为前缀，并将其余元素继续全排列，等到出口，出口出去后还需要还原数组；

排列（递归）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
/** permutaion: 排列。
 * 从n个数中选出m个数的方式，若不考虑顺序Cn(m)，若考虑顺序An(m)
 *//* 问题：密码破解
 * 假设有一个 4 位字母密码，每位密码是 a～e 之间的小写字。
 * 编写代码暴力破解密码。
 * 提示：根据可重复排列的规律，生成所有可能的 4 位密码。
 */

#include <iostream>
#include <vector>

using namespace std;
class Permutation {  
  private:  
    int resultCount_ = 0;  
  public:
  /** Details: 根据输入字母列表，获得所有的排列方式。
   *  params: result- 当前排列形式， candidate- 未排列字母表。
   *  return: null
   */
  void breakPassword(vector<string> result, vector<string> candidate) {    
    int len = candidate.size();    
    if (0 == len) {      
    // 无字母剩余，输出排列结果
      outputResult(result);
      resultCount_++;      
      return;
    }    
    for (int i = 0; i < len; i++) {      
      vector<string> resultNew;
      vector<string> candidateLeft;
      // 读取排列字母
      resultNew = result;
      resultNew.push_back(candidate[i]);      
      // 获得剩余字母表
      candidateLeft = candidate;   
      vector<string>::iterator it = candidateLeft.begin();
      candidateLeft.erase(it + i);      
      // 递归
      breakPassword(resultNew, candidateLeft);
    }
  }  
  // 输出结果  
  void outputResult(vector<string> result) {    
    for (unsigned int i = 0; i < result.size(); i++) {
      cout << result[i];
    }    
    cout << endl;
  }  
  // 获得所有可能密码总数    
  int getResultCount() {    
    return resultCount_;
  }
};
  int main(void) {  
    vector<string> fourAlphabetString = {"a", "b", "c", "d", "e"};  
    vector<string> res;
    Permutation test;
    test.breakPassword(res, fourAlphabetString);  
    cout << "可能的密码形式：";  
    cout << test.getResultCount() << "种" << endl;
  }

组合(数组)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
#include <string>
#include <vector>

using namespace std;

vector<string> &combination(vector<string> &res, const size_t &choose, string &working, const size_t &pos)
{
    if (choose > working.size() - pos)
        return res;
    for (size_t i = pos; i != working.size(); ++i)
    {
        working[i] = '0';
    }
    if (choose == 0 || pos == working.size())
    {
        res.push_back(working);
        return res;
    }
    working[pos] = '1';
    combination(res, choose - 1, working, pos + 1);
    working[pos] = '0';
    combination(res, choose, working, pos + 1);
    return res;
}

int main()
{
    vector<string> res;
    const size_t choose = 3;
    string working(5, '0');
    combination(res, choose, working, 0);
    for (size_t i = 0; i != res.size(); ++i)
    {
        cout << res[i] << '\t';
        for (size_t j = 0; j != working.size(); ++j)
        {
            if (res[i][j] == '1')
            {
                cout << j + 1 << ' ';
            }
        }
        cout << endl;
    }
    return 0;
}

组合(stl, vector)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <iostream>
#include <vector>
#include <algorithm>
#include <boost/assign.hpp>
#include <boost/function.hpp>

using namespace std;
using namespace boost;
using namespace boost::assign;

inline void print_(int t){cout<<t<<" ";}
inline void print(vector<int>& vec)
{
    for_each(vec.begin(),vec.end(),print_);
    cout<<endl;
}

//! 全排列测试
void test1()
{
    vector<int> vec;
    vec += 1,2,3,4,5,6,7,8;
    sort(vec.begin(),vec.end());
    int i = 0;
    do
    {
       print(vec);
       i++;
    }
    while(next_permutation(vec.begin(),vec.end()));
    std::cout<<i<<std::endl;//40320
}

//! 组合测试
size_t test2(int n,int m,boost::function<void(std::vector<int>& vec)> fn)
{
    vector<int> p,set;
    p.insert(p.end(),m,1);
    p.insert(p.end(),n-m,0);
    for(int i = 0;i != p.size();++i)
        set.push_back(i+1);
    vector<int> vec;
    size_t cnt = 0;
    do{
        for(int i = 0;i != p.size();++i)
            if(p[i])
               vec.push_back(set[i]);
        fn(vec);
        cnt ++;
        vec.clear();
    }while(prev_permutation(p.begin(), p.end()));
    return cnt;
}

int main()
{
    // test1();
    std::cout<<test2(20,3,print)<<std::endl;
    return 0;
}

组合（class，递归）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <cmath>
#include <iostream>
#include <vector>
using namespace std;
// 组合
// 思想：从一些对象n中选出一部分m(1<=m<=n)，不考虑顺序，可能的形式有几种。
// 应用：队伍参赛排序。自然语言处理中，处理输入词。当输入词相同仅顺序不一致时，
// 可以采用组合的概念将其排序，并认定为意思相同。

template<typename T> class Combination {  
private:  
  const int firstPrize;  
  const int secondPrize;  
  const int thirdPrize;  
public:
  Combination(int x, int y, int z)
      : firstPrize(x), secondPrize(y), thirdPrize(z) {
  }  
  /**
  * @description:
  * 从10个人中选出三等奖3人，二等奖2人，一等奖1人，不能重复获奖。
  * @param {type} rewardNum- 指定赏金数， result- 奖赏方式结果。
  * @return: null
  */
  void rewardMethods(vector<T> result, vector<T> candidate){    
    unsigned int len = thirdPrize + secondPrize + firstPrize;    
    if (result.size() == len) {      
      // 输出结果
      resultOutput(result);      
      return;
    } else {      
      for (unsigned int i = 0; i < candidate.size(); i++) {
        vector<int> resultNew = result;
        resultNew.push_back(candidate[i]); 
        vector<int> candidateNew;
        copyElem(candidate, candidateNew, i + 1);
        rewardMethods(resultNew, candidateNew);
      }
    }
  }  
  // 数据复制函数
  void copyElem(vector<T>& input, vector<T>& output, int i){    
    vector<int>::iterator it = input.begin() + i;    
    for (; it < input.end(); it++) {
      output.push_back(*it);
    }
  }  
  // 输出结果
  void resultOutput(vector<T> res) {    
    for (unsigned int i = 0; i < res.size(); i++) {      
      if (i == thirdPrize) cout << '*';     
      if (i == thirdPrize + secondPrize) 
      cout << '*';      
      cout << res[i] << ' ';
    }    
    cout << endl;
  }
};
  // test
  int main(void) {
    Combination <int> test(1, 2, 3);  
    vector<int> res;  vector<int> candidate;  
    // 输入
    for (unsigned int i = 0; i < 10; i++) {
      candidate.push_back(i + 1);
    }
    test.rewardMethods(res, candidate);
  }

可重复组合（运行Pass）

  • 允许元素重复的一类组合问题

  • 用P(n, k)表示从n个元素中选出k个元素（允许重复）的组合问题，那么此问题可以分解为两个子问题：P(n, k-1)和P(n-1, k)，

  • 解释如下：

    • P(n, k)中n个元素的所有k元素组合可以分成两部分。

    • 第一部分的每个组合均以第一个元素开始，再连接上k-1个元素的组合，即再连接上P(n,k-1)的每一个组合；

    • 第二部分的每个组合不含有第一个元素，即P(n-1, k)中的每一个组合（此时元素为后n-1个元素）。

    • 因此，P(n, k)分解为P(n, k-1)和P(n-1, k)。

如果用f(n, k)表示P(n, k)中的组合数，那么有：
（1）当k = 1时，f(n, k) = n
（2）当n = 1时，f(n, k) = 1
（3）当k > 1且n > 1时，f(n, k) = f(n, k -1) + f(n-1, k)

此外，有公式f(n, k) = C(n + k -1, k)（表示n+k-1选k的组合数，没有重复元素），这可以用归纳法证明，这里就不啰嗦了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
template <typename ElemType>
void CalcRepeatableCombination(const ElemType elements[], int num, int k, vector<ElemType> &pre, vector<vector<ElemType>> &result)
{
    if (k == 1)
    {
        for (int i = 0; i < num; i++)
        {
            // copy(pre.begin(), pre.end(), ostream_iterator<ElemType>(cout));
            // cout << elements[i];
            // cout << endl;
            vector<ElemType> tmp(pre.begin(), pre.end());
            tmp.push_back(elements[i]);
            result.push_back(tmp);
        }
        return;
    }
    if (num == 1)
    {
        // ostream_iterator<ElemType> outIter(cout);
        // outIter = copy(pre.begin(), pre.end(), outIter);
        // fill_n(outIter, k, elements[0]);
        // cout << endl;
        vector<ElemType> tmp(pre.begin(), pre.end());
        for (int i = 0; i < k; i++)
        {
            tmp.push_back(elements[0]);
        }
        result.push_back(tmp);
        return;
    }

    pre.push_back(elements[0]);
    CalcRepeatableCombination(elements, num, k - 1, pre, result);
    pre.pop_back();

    CalcRepeatableCombination(elements + 1, num - 1, k, pre, result);
}

template <typename ElemType>
void CalcRepeatableCombination(const ElemType elements[], int num, int k, vector<vector<ElemType>> &result)
{
    cout << " num=" << num << " k=" << k << endl;
    // assert(num >= k && k >= 1);
    assert(k >= 1);
    vector<ElemType> one;
    CalcRepeatableCombination(elements, num, k, one, result);
}

int main()
{
    char elements[] = {'a', 'b', 'c', 'd'};
    vector<char> com_r;
    CalcRepeatableCombination(elements, 4, 3, com_r);
}