我有一个情况，我有一个对列表，每个对都有两个数值。我想找到这些元素的子集，仅包含那些不被另一个元素的两个元素超过的对（比方说被另一个元素“黯然失色”）。 例如，对 (1,2) 被 (4,5) 掩盖，因为两个元素都小于另一对中的相应元素。
此外，(1,2) 被认为比 (1,3) 黯然失色，因为第一个元素等于另一个元素，而第二个元素小于另一个元素。
然而，(2, 10) 不会被 (9, 9) 掩盖，因为只有其中一个元素被另一个元素超过。
配对相同的情况应减少到只有一个（删除重复项）。
最终，我希望将配对列表减少到一个子集，其中仅保留未被任何其他配对所掩盖的配对。
例如，采用以下列表：
(1,2)
(1,5)
(2,2)
(1,2)
(2,2)
(9,1)
(1,1)
这应该减少到以下内容：
(1,5)
(2,2)
(9,1)
我在 python 中的最初实现如下，使用极坐标：
import polars as pl
pairs_list = [
(1,2),
(1,5),
(2,2),
(1,2),
(2,2),
(9,1),
(1,1),
]
# tabulate pair elements as 'a' and 'b'
pairs = pl.DataFrame(
data=pairs_list,
schema={'a': pl.UInt32, 'b': pl.UInt32},
orient='row',
)
# eliminate any duplicate pairs
unique_pairs = pairs.unique()
# self join so every pair can be compared (except against itself)
comparison_inputs = (
unique_pairs
.join(
unique_pairs,
how='cross',
suffix='_comp',
)
.filter(
pl.any_horizontal(
pl.col('a') != pl.col('a_comp'),
pl.col('b') != pl.col('b_comp'),
)
)
)
# flag pairs that were eclipsed by others
comparison_results = (
comparison_inputs
.with_columns(
pl.all_horizontal(
pl.col('a') <= pl.col('a_comp'),
pl.col('b') <= pl.col('b_comp'),
)
.alias('is_eclipsed')
)
)
# remove pairs that were eclipsed by at least one other
principal_pairs = (
comparison_results
.group_by('a', 'b')
.agg(pl.col('is_eclipsed').any())
.filter(is_eclipsed=False)
.select('a', 'b')
)
虽然这看起来确实有效，但由于自连接表的庞大规模，对于大型数据集来说，在计算上是不可行的。
我考虑过通过删除冗余的反向比较来过滤比较输入表，例如，X对与Y对以及Y对与X对不需要都像当前一样位于表中，但更改需要附加条件在每次比较中报告哪个元素在比较中黯然失色，并且仅将数据集减少一半，这并不那么重要。
我发现在执行自连接步骤之前，我可以通过执行窗口函数过滤器来大大减少所需的比较，该窗口函数过滤器仅过滤每个 a 的最大值 b，反之亦然。换句话说：
unique_pairs = (
pairs
.unique()
.filter(a = pl.col('a').last().over('b', order_by='a')
.filter(b = pl.col('b').last().over('a', order_by='b')
但是当然这只能做这么多并且取决于 a 和 b 的基数。之后我还需要自加入并比较才能得到结果。
我很好奇是否已经建立了一些算法来计算这个值，以及是否有人有更有效的方法的想法。无论如何，有兴趣了解更多。预先感谢。
des顺序排列，第一个元素中存在联系，然后按
des对第二个元素进行排序
unique_pairs = sorted(set(pairs), key=lambda x: (-x[0], -x[1]))
通过保持每对的条件 If - b 大于迄今为止所有具有较大第一个元素的对的最大第二个元素，该对不能被遮盖。
from typing import List, Tuple
import bisect
def find_non_eclipsed_pairs(pairs: List[Tuple[int, int]]) -> List[Tuple[int, int]]:
if not pairs:
return []
unique_pairs = sorted(set(pairs), key=lambda x: (-x[0], -x[1]))
result = []
max_second_elements = []
for pair in unique_pairs:
if not max_second_elements or pair[1] > max_second_elements[-1]:
result.append(pair)
while max_second_elements and max_second_elements[-1] <= pair[1]:
max_second_elements.pop()
max_second_elements.append(pair[1])
return sorted(result)
测试
def test_pareto_pairs():
test_cases = [
(
[(1,2), (1,5), (2,2), (1,2), (2,2), (9,1), (1,1)],
[(1,5), (2,2), (9,1)]
),
(
[],
[]
),
(
[(1,1)],
[(1,1)]
),
(
[(1,1), (2,2), (3,3), (4,4)],
[(4,4)]
),
(
[(1,5), (5,1)],
[(1,5), (5,1)]
),
(
[(1,1), (1,2), (2,1), (2,2), (3,1), (1,3)],
[(1,3), (2,2), (3,1)]
)
]
for i, (input_pairs, expected) in enumerate(test_cases, 1):
result = find_non_eclipsed_pairs(input_pairs)
assert result == sorted(expected), f"Test case {i} failed: expected {expected}, got {result}"
print(f"Test case {i} passed")
if __name__ == "__main__":
test_pareto_pairs()
pairs_list = [
(1,2),
(1,5),
(2,2),
(1,2),
(2,2),
(9,1),
(1,1),
]
result = find_non_eclipsed_pairs(pairs_list)
print("\nOriginal pairs:", pairs_list)
print("Non-eclipsed pairs:", result)
哪些结果
=================== RESTART: C:/Users/Bhargav/Desktop/test.py ==================
Test case 1 passed
Test case 2 passed
Test case 3 passed
Test case 4 passed
Test case 5 passed
Test case 6 passed
Original pairs: [(1, 2), (1, 5), (2, 2), (1, 2), (2, 2), (9, 1), (1, 1)]
Non-eclipsed pairs: [(1, 5), (2, 2), (9, 1)]