不固定長度的 2D array 用 recursion 跑出所有組合

同事工作上遇到一個問題, 就是當不固定的 2d array 或是

不固定長度的數個 list 然後頭互串, 形成像是

A1->A2->A3, B1->B2 且 A1->B1 時

若要用 recursive 把所有的組合印出, 要怎麼處理?

最終我們要的答案是:

A1 B1, A2 B1, A3 B1, A1 B2, A2 B2, A3 B2

所以我的想法是很直觀的利用 recursive 做, 內容就是 先右再下 直到跑完所有情況

然後很不熟 template 的我就寫了這個很骯髒的程式, 請大大不要鞭太大力

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
#include <iostream>
#include <string>
#include <cstdlib>
#include <sstream>

using namespace std;

template < int secondDim, int thirdDim >
void recurMap( const int (&map)[ secondDim ][ thirdDim ], const int &i, const int &j, string &str ) {
string temp = str;

if( i >= secondDim or j >= thirdDim or map[ i ][ j ] == -1 ) {
if( map[ i ][ j ] != -1 ) cout << temp << endl;
return;
}

stringstream ss;
ss << map[ i ][ j ];
temp += ss.str() + "\t";

recurMap( map, 0, j+1, temp );
recurMap( map, i+1, j, str );
}

int main() {
int map[4][4] = { 0, 1, 2, 3, 10, 11, 12, 13, 20, 21, -1, 23, 31, -1, -1, -1  };

cout << "MAP" << endl;

for( int i = 0 ; i < 4; i++ ) {
for( int j = 0 ; j < 4; j++ ) {
cout << map[ i ][ j ] << "\t";
}
cout << endl;
}
cout << endl;

cout << "RST" << endl;

string tmp = "";
recurMap( map, 0, 0, tmp );

return 0;
}

Leave a Reply

Your email address will not be published. Required fields are marked *