I have structs that contain integer values x and y.
I have two equal struct lists, A[] and B[], and my constraint is that they must stay ordered by x.
My challenge is that I need to determine, for any index, if the y value for list B[] is greater than the y value for list A[].
The confusing thing is that you can swap the positions of the structs as long as x is in order.
It's a difficult thing to explain, so I'll give an example.
A[] |
B[] |
Index | Comparison | Pass/Fail |
|---|---|---|---|---|
struct{x = 1, y = 1} |
struct{x = 1, y = 2} |
0 | 1 > 2 | pass |
struct{x = 2, y = 1} |
struct{x = 2, y = 2} |
1 | 1 > 2 | pass |
struct{x = 3, y = 1} |
struct{x = 3, y = 2} |
2 | 1 > 2 | pass |
The table above works, because when the x values are in order, the y values in A[] are less than the y values in B[].
But for the example
A[] |
B[] |
Index | Comparison | Pass/Fail |
|---|---|---|---|---|
struct{x = 1, y = 1} |
struct{x = 1, y = 2} |
0 | 1 < 2 | pass |
struct{x = 2, y = 3} |
struct{x = 2, y = 7} |
1 | 3 < 7 | pass |
struct{x = 3, y = 6} |
struct{x = 2, y = 4} |
2 | 6 > 4 | fail |
Index 1 and 2 from B[] can be swapped, while still being in order with respect to x. If we swap the order to:
A[] |
B[] |
Index | Comparison | Pass/Fail |
|---|---|---|---|---|
struct{x = 1, y = 1} |
struct{x = 1, y = 2} |
0 | 1 < 2 | pass |
struct{x = 2, y = 3} |
struct{x = 2, y = 4} |
1 | 3 < 4 | pass |
struct{x = 3, y = 6} |
struct{x = 2, y = 7} |
2 | 6 < 7 | pass |
the y values in A[] will be less than the y values in same index in B[].
Is there any specific algorithm I should be searching for? Should I permutate through all possible combinations, and then check if it matches my requirements, or is there a way to permutate specific values while staying in-order?