Combinations from 3d array picking one element from each array

AkshayMalige (20)
I want to get the combinations from 3d array of fixed size picking one element from second dimension. I cannot use vectors or any dynamic memory object since code will be synthesized to hld and implemented in a hardware. Also no exotic c++ functions. The goal is to have as lowest possible execution time. Sorry about the limitations.

Example

int arr_in[8][3][2]; //fixed size

if the 3rd dim has has [0,0] i do not consider them in my combinations.(I do not/will not have a case where one element is 0 ([0,1]))

1
2
3
4
5
6
7
8
9
 
Input : 
[ [[1,2],[0,0],[0,0]],  
  [[3,4],[0,0],[0,0]],  
  [[5,6],[7,8],[0,0]],  
  [[9,10],[0,0],[0,0]],  
  [[11,12],[0,0],[0,0]],  
  [[13,14],[0,0],[0,0]],  
  [[15,16],[0,0],[0,0]],  
  [[17,18],[0,0],[0,0]]  ]


Output : valid solutions
1
2
 
a: [1,2],[3,4],[5,6],[9,10],[11,12],[13,14],[15,16],[17,18]
b: [1,2],[3,4],[7,8],[9,10],[11,12],[13,14],[15,16],[17,18]
Last edited on
ne555 (10692)
¿how are you storing all these arrays of different length?

supposing a big matrix (oversizing, wasting memory)
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
 
struct Select{
	int indices[rows];
	void next(){
		//counting, like in elementary school
		int K=0;
		bool carry = false;
		do{
			++indices[K];
			if (indices[K] % size[K]){
				carry = true;
				indices[K] = 0;
				++K;
			}
			else
				carry = false;
		}while(K<rows and carry);
	}
};

Select s;
//getting one combination
T selection[rows]; 
for(int K=0; K<rows; ++K)
	selection[K] = matrix[K][s.indices[K]];
s.next();

Last edited on
AkshayMalige (20)
@ne555,
Thanks for the interest.
You question is very valid. I dont have arrays of variable length, its fixed. For the sake of the simplicity of the question i just framed it wrong. I have edited the question now.
Last edited on
lastchance (6980)
Your edited question is incomplete and doesn't accord with your output - why are there no 0's in your model output? If you have 3 arrays, each of length 3, then a counting-based method would produce 3*3*3=27 outputs.

Are all arrays of the same length? What (if anything) do you do about repeats?

BTW, don't double-post. I suggest removing the duplicate post that you have created in the Beginners section.
AkshayMalige (20)
Thanks for the warning about the double post(removed it). My failed attempt to simplify the question has made it very misleading. I have now rephrased the question to actuality of the problem. Thanks

salem c (3700)
Formatted for some clarity.
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
 
Input : 
[
  [[1,2],  [0,0],[0,0]],
  [[3,4],  [0,0],[0,0]],
  [[5,6],  [7,8],[0,0]],
  [[9,10], [0,0],[0,0]],
  [[11,12],[0,0],[0,0]],
  [[13,14],[0,0],[0,0]],
  [[15,16],[0,0],[0,0]],
  [[17,18],[0,0],[0,0]]
]

Output : two solutions

a: 
[1,2],
[3,4],
[5,6],
[9,10],
[11,12],
[13,14],
[15,16],
[17,18]

b: 
[1,2],
[3,4],
[7,8],
[9,10],
[11,12],
[13,14],
[15,16],
[17,18]


When you say there are 'two' solutions, are you saying
- I want all possible solutions.
- I want any single valid solution.


AkshayMalige (20)
Thank you for the formatting . When i say two solutions i mean I want all possible valid solutions.
Last edited on
dhayden (5798)
Here's code that produces the output you've listed. For each column, it finds the first row with a non-zero entry. Then it swaps that entry into the corresponding entry of column 1, prints it, and swaps it back to restore the value.
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
 
#include <iostream>
#include <algorithm>
using std::cout;

constexpr int DIMX=8, DIMY=3, DIMZ=2;
int arr[DIMX][DIMY][DIMZ] =
    { {{1,2},{0,0},{0,0}},  
      {{3,4},{0,0},{0,0}},  
      {{5,6},{7,8},{0,0}},  
      {{9,10},{0,0},{0,0}},  
      {{11,12},{0,0},{0,0}},  
      {{13,14},{0,0},{0,0}},  
      {{15,16},{0,0},{0,0}},  
      {{17,18},{0,0},{0,0}}
    };

// Process a solution, which is arr[][col]
void process(int col)
{
    for (int row=0; row<DIMX; ++row) {
	if (row) cout << ',';
	cout << '[' << arr[row][col][0];
	for (int z=1; z<DIMZ; ++z) {
	    cout << ',' << arr[row][col][z];
	}
	cout << ']';
    }
    cout << '\n';
}

int main()
{
    constexpr int printCol = 0;	// the column to print
    
    for (int col=0; col<DIMY; ++col) {
	// Find the first row with a non-zero entry
	for (int row=0; row<DIMX; ++row) {
	    if (arr[row][col][0]) {
		// Found one. Swap this entry with the print
		// column and print it
		std::swap(arr[row][col], arr[row][printCol]);
		process(printCol);

		// Swap it back to restore.
		std::swap(arr[row][col], arr[row][printCol]);
		break;
	    }
	}
    }
}

The fastest way to do this probably depends on the actual dimensions of the array.
- Consider swapping the rows and columns. That way, when you process a solution, you're going through sequential memory.
- If the 3rd dimension is actually large, then swapping the entries might be too expensive.
AkshayMalige (20)
Thank you very much.
I see a problem here. This fails when i have more than 1 columns with non-zero pairs.
It considers only the combinations from the first non-zero pair row.

For example, for the below input i must expect 6 valid combinations, while i get only 3

1
2
3
4
5
6
7
8
9
10
11
 
constexpr int DIMX=8, DIMY=3, DIMZ=2;
int arr[DIMX][DIMY][DIMZ] =
    { {{1,2},{22,23},{33,34}},  
      {{3,4},{0,0},{0,0}},  
      {{5,6},{7,8},{0,0}},  
      {{9,10},{0,0},{0,0}},  
      {{11,12},{0,0},{0,0}},  
      {{13,14},{0,0},{0,0}},  
      {{15,16},{0,0},{0,0}},  
      {{17,18},{0,0},{0,0}}
    };


Output:
1
2
3
 
[1,2],[3,4],[5,6],[9,10],[11,12],[13,14],[15,16],[17,18]
[22,23],[3,4],[5,6],[9,10],[11,12],[13,14],[15,16],[17,18]
[33,34],[3,4],[5,6],[9,10],[11,12],[13,14],[15,16],[17,18]



salem c (3700)
Would a row like this be a thing?
 
 
    { {{1,2},{0,0},{33,34}},

Or are all the zeros in effect padding to the right of what are variable length rows of data.
AkshayMalige (20)
No, { {{1,2},{0,0},{33,34}}, such a row are not a thing, they are always sorted. hence if there is {0,0} it will be the last (3rd) element.

This problem was earlier being solved using vectors as shown in the link https://www.cplusplus.com/forum/general/248001/#msg1093629 , but since i have to synthesize this into a FPGA i cannot use vectors.
Last edited on
salem c (3700)
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
 
$ cat baz.cpp
#include <iostream>
#include <string>
#include <sstream>
using namespace std;

constexpr int DIMX=8, DIMY=3, DIMZ=2;

void foo( int arr[DIMX][DIMY][DIMZ], int depth, const string &result ) {
  if ( depth == DIMX ) {
    cout << result << endl;
    return;
  }
  for ( int i = 0 ; i < DIMY ; i++ ) {
    if ( arr[depth][i][0] ) {
      ostringstream os;
      os << "[" << arr[depth][i][0] << "," << arr[depth][i][1] << "]";
      string t = result + (result.length() > 0 ? "," : "") + os.str();
      foo(arr,depth+1,t);
    } else {
      return;
    }
  }
}


int main()
{
  int arr[DIMX][DIMY][DIMZ] =
      { {{1,2},{22,23},{33,34}},
        {{3,4},{0,0},{0,0}},
        {{5,6},{7,8},{0,0}},
        {{9,10},{0,0},{0,0}},
        {{11,12},{0,0},{0,0}},
        {{13,14},{0,0},{0,0}},
        {{15,16},{0,0},{0,0}},
        {{17,18},{0,0},{0,0}}
      };
  foo(arr,0,"");
  return 0;
}
$ g++ -std=c++11 baz.cpp
$ ./a.out 
[1,2],[3,4],[5,6],[9,10],[11,12],[13,14],[15,16],[17,18]
[1,2],[3,4],[7,8],[9,10],[11,12],[13,14],[15,16],[17,18]
[22,23],[3,4],[5,6],[9,10],[11,12],[13,14],[15,16],[17,18]
[22,23],[3,4],[7,8],[9,10],[11,12],[13,14],[15,16],[17,18]
[33,34],[3,4],[5,6],[9,10],[11,12],[13,14],[15,16],[17,18]
[33,34],[3,4],[7,8],[9,10],[11,12],[13,14],[15,16],[17,18]


Turning the recursion into a loop is left as an exercise for the reader.
AkshayMalige (20)
Thank you very much. This works totally fine for me. you made it a lot simpler than i thought.

I just removed the string part so that the output can be accessible. 

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
 
#include <iostream>
#include <string>
#include <sstream>
using namespace std;

constexpr int DIMX=8, DIMY=3, DIMZ=2;

void foo( int arr[DIMX][DIMY][DIMZ], int depth ,int res[DIMX][DIMZ]) {
  if ( depth == DIMX ) {
                for(int j=0; j<depth; j++){
                cout << "{" << res[j][0] << "," << res[j][1] << "}";
            }
    cout<<endl;
    return;
  }
  for ( int i = 0 ; i < DIMY ; i++ ) {
    if ( arr[depth][i][0] ) {
        res[depth][0]= arr[depth][i][0];
        res[depth][1]= arr[depth][i][1];
        foo(arr,depth+1,res);
    } else {
      return;
    }
  }
}


int main()
{
  int arr[DIMX][DIMY][DIMZ] =
      { {{1,2},{10,20},{30,40}},
        {{3,4},{0,0},{0,0}},
        {{5,6},{50,60},{70,80}},
        {{9,10},{0,0},{0,0}},
        {{11,12},{0,0},{0,0}},
        {{13,14},{0,0},{0,0}},
        {{15,16},{0,0},{0,0}},
        {{17,18},{0,0},{0,0}}
      };
      
      int res[DIMX][DIMZ]= {{0,0},{0,0},{0,0},{0,0},{0,0},{0,0},{0,0},{0,0}};

        foo(arr,0,res);
  return 0;
}


Output:
1
2
3
4
5
6
7
8
9
 
{1,2}{3,4}{5,6}{9,10}{11,12}{13,14}{15,16}{17,18}
{1,2}{3,4}{50,60}{9,10}{11,12}{13,14}{15,16}{17,18}
{1,2}{3,4}{70,80}{9,10}{11,12}{13,14}{15,16}{17,18}
{10,20}{3,4}{5,6}{9,10}{11,12}{13,14}{15,16}{17,18}
{10,20}{3,4}{50,60}{9,10}{11,12}{13,14}{15,16}{17,18}
{10,20}{3,4}{70,80}{9,10}{11,12}{13,14}{15,16}{17,18}
{30,40}{3,4}{5,6}{9,10}{11,12}{13,14}{15,16}{17,18}
{30,40}{3,4}{50,60}{9,10}{11,12}{13,14}{15,16}{17,18}
{30,40}{3,4}{70,80}{9,10}{11,12}{13,14}{15,16}{17,18}




Last edited on
AkshayMalige (20)
Okay, since recursion cannot be synthesized in hardware,Finally I had to rewrite the solutions i found here in a different way. May be will help someone.
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
69
70
71
72
73
74
75
76
77
78
79
80
 
#include <iostream>
using namespace std;

constexpr int DIMX=8, DIMY=3, DIMZ=2, MAX_COMB=50;
void index_count( int arr[DIMX][DIMY][DIMZ],int res[DIMX]) {
    for(int i=0; i< DIMX; i++){
        for(int j=0;j<DIMY; j++){
            arr[i][j][0] >0 ? res[i]++ : res[i];
        }
    }
}

int check_decri(int res[DIMX]){
    for (int i=0; i<DIMX; i++){
        if (res[i] > 1){
            return i;
            break;
        }
    }
    return DIMX;
}

int index_comb(int res[DIMX],int arr_index[MAX_COMB][DIMX]){
    int original[DIMX];
    for(int a=0; a< DIMX; a++){
        original[a]= res[a];
    }
    int first = check_decri(res);
    int no_comb=0;
    while(check_decri(res) !=8){
        int current = check_decri(res);
        for(int i=0; i<DIMX; i++){
            arr_index[no_comb][i]=res[i];
        }
        res[check_decri(res)] -=1;
        no_comb++;
        if(first != current ){
            for(int j=0; j< current; j++){
                res[j]= original[j];
            }
        }
    }
    return no_comb;
}


int main()
{
    int arr[DIMX][DIMY][DIMZ] =
        { {{1,2},{10,20},{30,40}},
        {{3,4},{0,0},{0,0}},
        {{5,6},{0,0},{0,0}},
        {{9,10},{0,0},{0,0}},
        {{11,12},{90,100},{0,0}},
        {{13,14},{0,0},{0,0}},
        {{15,16},{0,0},{0,0}},
        {{17,18},{0,0},{0,0}}
    };
 
    int res[DIMX]= {0,0,0,0,0,0,0,0};

    index_count(arr,res);
    
    int arr_index[MAX_COMB][DIMX];
    cout<<"No of combinations :  ";
    int no_of_comb= index_comb(res,arr_index);
    
    for(int i=0; i<DIMX; i++){
        arr_index[no_of_comb][i]=res[i];
    }
    cout<<no_of_comb<<endl;
    for(int j=0; j<no_of_comb+1; j++){
        for(int k=0; k<DIMX; k++){
            cout<<"{"<<arr[k][arr_index[j][k]-1][0]<<","<<arr[k][arr_index[j][k]-1][1]<<"}"<<" ";
        }
        cout<<endl;
    }

 return 0;
}


Output:
1
2
3
4
5
6
7
 
No of combinations :  5
{30,40} {3,4} {5,6} {9,10} {90,100} {13,14} {15,16} {17,18} 
{10,20} {3,4} {5,6} {9,10} {90,100} {13,14} {15,16} {17,18} 
{1,2} {3,4} {5,6} {9,10} {90,100} {13,14} {15,16} {17,18} 
{30,40} {3,4} {5,6} {9,10} {11,12} {13,14} {15,16} {17,18} 
{10,20} {3,4} {5,6} {9,10} {11,12} {13,14} {15,16} {17,18} 
{1,2} {3,4} {5,6} {9,10} {11,12} {13,14} {15,16} {17,18}

Last edited on
Topic archived. No new replies allowed.