Array Path Combinations

[dvongrad]

I'm not sure how to title the question I have so I can't be certain this hasn't been answered before. That said, following is a description of my programming question.

I have a class R containing 2 integer elements, say X and Y. I then have two 24 element arrays named A and B where each element contains an instance of class R. I would like to iterate through the arrays to determine how to use R.Y to populate a third array C as follows:

If R.Y at index i of A is larger than R.Y at index i of B then put R from A into index i of C.

If R.Y at index i of B is larger than R.Y at index i of A then put R from B into index i of C.

If R.Y at index i of A is equal to R.Y at index i of B then put either R into index i of C.

It's the third of these conditions that has me perplexed. For example, if indexes 7, 15, and 19 of arrays A and B have R.Y equal to each other, then I want to try each element of both A and B at those indexes in C to determine which one is required based on a CRC check of C. So I could put the following R values into the same index values of C:

A[7], A[15], A[19]
A[7], A[15], B[19]
A[7], B[15], A[19]
A[7], B[15], B[19]
B[7], A[15], A[19]
B[7], A[15], B[19]
B[7], B[15], A[19]
B[7], B[15], B[19]

These 8 combinations come from 2^3 (2 arrays to the power of the number of times R.Y are the same), so if I have 4 indexes in A and B where R.Y are equal, then there would be 16 combinations, 5 indexes = 32 combinations, 6 = 64, etc.

The issue is I'll never know how many times R.Y will be identical in A and B for all the indexes; it could be 0 to 24. So to make a long description short, I need an algorithm to populate C with all the possible R classes from A and B where R.Y are equal in both arrays, iterate through all the possible combinations of C and stop when that first instance of C passes the CRC check.

Sound simple? I hope so. Let me know if you need any further clarification or point me to a thread that has something similar to this already answered. TIA

[L7Sqr]

I'm not understanding why you are including a crc check here. It seems to me (from the description) that if you have the following

A[ 1, 2, 3, 4, 5, 6, 7 ]
B[ 4, 2, 1, 5, 4, 6, 2 ]

Then your final array should be

C[ 4, 2, 3, 5, 5, 6, 7 ]

Where indexes 1 and 5 could be copied from either A or B.

Am I missing something?

[mike_2000_17]

>>Sound simple?
Not simple, but only a little twisted.

I'll ignore the fact that "Sound simple?" is the only question you asked, and I'll go ahead and give you some hints by solving a similar problem.

Long story short, the solution to your problem lies in "recursion" (a function that calls itself). Let me show a little "Hello World" decoding program. Assume you have an array of numbers, each number corresponds a letter, but lets assume that one of those numbers can correspond to two possible letters (thus creating this combinatorial problem). So, lets say that 0 = 'H', 1 = 'e', 2 = 'l' or 'o', 3 = <space>, 4 = 'W', 5 = 'r' and 6 = 'd', that would be enough to "encode" the "Hello World" message into the array {0,1,2,2,2,3,4,2,5,2,6}. To decode the array, until I find a match for the "Hello World" string, I could do the following recursive function:

#include <iostream>
#include <cstring>

const char actual_message[] = "Hello World";
const int encoded_message[] = {0,1,2,2,2,3,4,2,5,2,6};
const int num_characters = 11;

bool decodeMessage(char* CurrentGuess, int index) {
  while( index < num_characters ) {
    switch (encoded_message[index]) {
      case 0:
        CurrentGuess[index] = 'H';
        break;
      case 1:
        CurrentGuess[index] = 'e';
        break;
      case 2:
        {
          CurrentGuess[index] = 'l'; //start a branch for the 'l' possibility.
          if(decodeMessage(CurrentGuess, index + 1))
            return true; //if it worked, then return true.
          //if it didn't work, recurse on the 'o' branch.
          CurrentGuess[index] = 'o';
          return decodeMessage(CurrentGuess, index + 1); 
        };
        break;
      case 3:
        CurrentGuess[index] = ' ';
        break;
      case 4:
        CurrentGuess[index] = 'W';
        break;
      case 5:
        CurrentGuess[index] = 'r';
        break;
      case 6:
        CurrentGuess[index] = 'd';
        break;
      default:
        CurrentGuess[index] = '?';
        break;
    };
    index++; //move to the next character if all went well.
  };
  return strcmp(CurrentGuess,actual_message) == 0; //check if the message corresponds to the actual message.
};

int main() {
  char decoded_message[12];
  decoded_message[11] = '\0'; //null-termination.

  decodeMessage(decoded_message,0); //start the decoding.
  std::cout << "Message was found to be: '" << decoded_message << "'" << std::endl;

  return 0;
};

I hope, you can infer, from the above, what you would have to do for your tasks, which is very similar to this little Hello World decoder.

[dvongrad]

While I am comparing R.Y in the arrays A and B, the CRC check is actually being done on R.X in those arrays. I apologize for not making this clear. What I really was after was finding all the combinations of A and B being used in C for the CRC check. I came across the following pseudocode on another forum that does exactly what I want, with no recursion at all. Thanks for your input, though.

start with empty L;
for(i=0 to 23) put A or B in C (whichever has larger Y) *or* add i to L (if A.y and B.y match)
let n=length of L;
for (x=0 to (1<<n)-1)
for(b=0 to n-1)
test x&(1<<b), if clear put A[L] in C[L], or put B[L] in C[L]
endloop
test this array C // CRC check
endloop