英文:
Permutating all possible combinations while staying sorted?
问题
我有包含整数值 x 和 y 的结构体。
我有两个相等的结构体列表，A[] 和 B[]，我的约束是它们必须按照 x 的顺序排列。
我的问题是，对于任何索引，我需要确定列表 B[] 中的 y 值是否大于列表 A[] 中的 y 值。
令人困惑的是，只要 x 是有序的，你可以交换结构体的位置。
这个问题很难解释，所以我会举个例子。
A[] |
B[] |
索引 | 比较 | 通过/失败 |
|---|---|---|---|---|
struct{x = 1, y = 1} |
struct{x = 1, y = 2} |
0 | 1 < 2 | 通过 |
struct{x = 2, y = 1} |
struct{x = 2, y = 2} |
1 | 1 < 2 | 通过 |
struct{x = 3, y = 1} |
struct{x = 3, y = 2} |
2 | 1 < 2 | 通过 |
上面的表格是有效的，因为当 x 值有序时，A[] 中的 y 值小于 B[] 中的 y 值。
但对于下面的例子：
A[] |
B[] |
索引 | 比较 | 通过/失败 |
|---|---|---|---|---|
struct{x = 1, y = 1} |
struct{x = 1, y = 2} |
0 | 1 < 2 | 通过 |
struct{x = 2, y = 3} |
struct{x = 2, y = 7} |
1 | 3 < 7 | 通过 |
struct{x = 3, y = 6} |
struct{x = 2, y = 4} |
2 | 6 > 4 | 失败 |
B[] 中的索引 1 和 2 可以交换位置，同时仍然按照 x 的顺序排列。如果我们交换顺序为：
A[] |
B[] |
索引 | 比较 | 通过/失败 |
|---|---|---|---|---|
struct{x = 1, y = 1} |
struct{x = 1, y = 2} |
0 | 1 < 2 | 通过 |
struct{x = 2, y = 3} |
struct{x = 2, y = 4} |
1 | 3 < 4 | 通过 |
struct{x = 3, y = 6} |
struct{x = 2, y = 7} |
2 | 6 < 7 | 通过 |
A[] 中的 y 值将小于 B[] 中相同索引位置的 y 值。
我应该搜索什么特定的算法？我应该遍历所有可能的组合，然后检查是否满足我的要求，还是有一种方法可以在保持有序的情况下遍历特定的值？
英文:
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?
答案1
得分: 1
如果我正确理解你的问题，你可以简单地按照 x 和 y 对 A 和 B 进行排序。如果排序通过，那么你就得到了答案。如果排序未通过，那么你可以证明无法重新排序两个列表以通过排序。
英文:
If I understand your problem correctly, you can simply sort both A and B by x then y. If that passes, you have your answer. If that fails to pass, then you can prove that there is no way to reorder both lists to get a pass.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论