Combinations from 3d array picking one element from each array

[AkshayMalige]

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]))

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

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]

[ne555]

¿how are you storing all these arrays of different length?

supposing a big matrix (oversizing, wasting memory)

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();

[AkshayMalige]

@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.

[lastchance]

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]

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]

Formatted for some clarity.

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]

Thank you for the formatting . When i say two solutions i mean I want all possible valid solutions.

[dhayden]

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.

#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]

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

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,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]

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]

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.

[salem c]

$ 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]

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.

#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}{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}

[AkshayMalige]

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.

#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:

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}