回答此问题可获得 20 贡献值,回答如果被采纳可获得 50 分。
<p>我有一个需要订购的成对对象的列表,必须合并相邻的成对对象。输入列表中对的原始顺序是随机的,没有重要性。在每一对中,我们可以确定第一个值永远不会大于第二个值。
看看这个例子中的整数</p>
<pre><code>lst = [[1, 4], [17, 20], [2, 3], [16, 18], [6, 6], [6, 7], [9, 13], [21, 24]]
</code></pre>
<p>如果出现以下情况,两对应合并:</p>
<ul>
<li>它们是重叠的,例如[16,18]和[17,20]->;[16,20]</li>
<li>他们是近邻,例如[17,20]和[21,24]->;[17,24]</li>
<li>具体来说[6,6]和[6,7]也应该合并,成为[6,7]</li>
</ul>
<p>然后对所有对进行排序(这很容易),因此查看示例数据,最终结果为:</p>
<pre><code>ref = [[1, 4], [6, 7], [9, 13], [16, 24]]
</code></pre>
<p>我有一个函数mrg2pairs(pair_a,pair_b),它将返回一个或两个pair的列表。如果合并合适,则返回一个合并对,否则返回列表中的原始两对。
这就解决了2对的情况,我希望找到一种平滑的方法来处理较长的列表。
也许是递归的,使用mrg2pairs(),但我无法想象解决方案</p>
<pre><code>def mrg2pairs(pair_a, pair_b):
""" Merge two pairs
:param pair_a: First pair
:param pair_b: Second pair
:return: A list of, one or two, pairs, each same format as pair_a and pair_b
"""
a1, a2 = pair_a[0], pair_a[1]
b1, b2 = pair_b[0], pair_b[1]
if a1 < b1:
if (b1 - a2) > 1: # a entirely before b
return [pair_a, pair_b] # return untouched
elif a2 == b1: # a-end touching b-start
return [[a1, b2]] # merge
else:
if a2 < b2: # a overlapping b-start
return [[a1, b2]]
else: # a encapsulating b
return [pair_a] # return a
else:
if a1 < b2:
if a2 > b2: # a overlapping b-end
return [[b1, a2]]
else: # a inside b
return [pair_b] # return b
else:
if (a1 - b2) > 1: # a entirely after b
return [pair_a, pair_b] # return untouched
else: # a-start touching b-end
return [[b1, a2]] # merge
</code></pre>
<p>该函数经过测试,工作正常-问题是如何在列表情况下从2线对情况转到n线对情况</p>
<p>我需要用Python解决这个问题-欢迎任何建议,但我更喜欢Python优雅</p>