print combinatorics

Posted on |

combinatorics related algorithms e.g. unique BST(leetCode95), Permutations(46), Unique Path(62). Give an integer m, how many different combinations can have? mathematically, it’s a permutation P_m^m or combination C_m^n problem, the total number is easy to calculate, but how to write a code to print out each combination elegantly ?

one core step: how to generate a new combination(k+1) array by inserting one new element into the current combination(k). e.g. 

{1, 2} --> {3, 1, 2}, {1, 3, 2}, {1, 2, 3}

here is basically insert 3 at (k+1) positions, and each new position will generate a new combination with (k+1) size. depends on the problem, choose either vector(to support random access) or list (to support O(1) insert or delete) as the container.

one tip here, how to erase one element from std::list while iterating ?

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
vector<list<int>>  next_layer(vector<list<int>>& layer, int c)
{
	if(layer.empty())
	{
		list<int> tmp ;
		tmp.push_back(c);
		layer.push_back(tmp);
		return layer;
	}
	
	vector<list<int>> next_layer_v, cur; 
	for(int i=0; i<layer.size(); i++)
	{
		list<int>::iterator lit ;
		list<int>  arr = layer[i] ; 
		cur.clear();
		for(lit = arr.begin(); lit != arr.end(); lit++)
		{
 			arr.insert(lit, c); //insert c in front of lit
   			cur.push_back(arr);
   			lit = arr.erase(--lit);  // erase c, which is 1 step in front of lit, and must return lit here, else lit will become non-refereable 
		}
	
	 	next_layer_v.insert(next_layer_v.end(), cur.begin(),  cur.end()); 
	}
	
	return next_layer_v; 
}
void sol(int num)
{
  vector<list<int> > layer, last_layer;
  list<int>  cur_list ;
  for(int i=0; i< num; i++)
  {
	  layer = next_layer(last_layer, i);
	  last_layer = layer;
  }
  print_vec_list(layer);
}

this implementation is more clear than what I did in Permutation

while the memory of many last layers vector> actually are not in using. how to recycle the memory ?

1
2
3
4
vector<list<int>>().swap(layer);
//or -std=c++11
layer.resize(0);
layer.shrink_to_fit();