<p>我建议的解决方案是首先尝试“链接”尽可能多的对,以形成可以互换的索引集-例如在第一个示例中,<code>[[1, 4], [3, 4]]</code>可以变成{<cd2>}。然后,这些索引子集中的每一个子集都可以按字典顺序排序以形成输出。实施过程如下:</p>
<pre><code>def build_permitted_subs(pairs):
perm = []
for a, b in pairs:
merged = False
for ind, sub_perm in enumerate(perm):
if a in sub_perm or b in sub_perm:
sub_perm.add(a)
sub_perm.add(b)
merged = True
break
else:
perm.append(set([a, b]))
if merged:
for merge_perm_ind in reversed(range(ind + 1, len(perm))):
if perm[merge_perm_ind] & sub_perm:
sub_perm.update(perm[merge_perm_ind])
perm.pop(merge_perm_ind)
return list(map(sorted, perm))
def swap_lex_order(swap_str, _pairs):
pairs = [[a - 1, b - 1] for a, b in _pairs]
out = list(swap_str)
perm = build_permitted_subs(pairs)
for sub_perm in perm:
sorted_subset = sorted(sub_perm, key=lambda ind: swap_str[ind], reverse=True)
for sort, targ in zip(sorted_subset, sub_perm):
out[targ] = swap_str[sort]
return "".join(out)
print(swap_lex_order("dznsxamwoj", [[1, 2], [3, 4], [6, 5], [8, 10]]))
print(swap_lex_order("abdc", [[1, 4], [3, 4]]))
print(swap_lex_order("acxrabdz",[[1,3], [6,8], [3,8], [2,7]]))
</code></pre>
<p>带输出:</p>
^{pr2}$
<p>我还将参数重命名为不使用<code>str</code>,这已经是一个非常基本的Python内置。请注意,我的代码可能不是尽可能的Pythonic,但是我认为它可以很好地演示算法,而且它不会受到任何性能的严重影响。我怀疑这种方法的复杂度很低-它通常是“智能”的,因为它不会对任何东西进行暴力攻击,并且使用<code>O(n log n)</code>排序。第一个例子似乎是正确的。请注意,这会将每个对转换为基于0的,因为这对于Python来说更容易。在</p>
<p>这有点依赖于能够从相邻的排列(交换对)中形成任何排列(对链接的对进行排序)。这可能不是完全直观的,但它可能有助于您认识到,您可以仅使用列表中相邻的交换来有效地执行插入(通过在要执行的方向上不断交换元素)。使用相邻交换排列列表的一个例子是bubblesort,您可能意识到,如果任何置换都可以进行bubblesort,那意味着所有的置换都可以通过bubblesort来实现。在</p>
<p>如果您有任何问题,或者任何东西不起作用,请告诉我,我将开始详细说明/调试。(截至格林尼治标准时间19:28,我已经注意到一个bug并将其编辑掉:)。Bug#2(测试用例3有重复的z)也应该被修复。在</p>
<p>关于bug#1的更多信息:</p>
<p>我没有对<code>build_permitted_subs</code>返回的索引进行排序,因此它无法参照<code>swap_str</code>对它们进行正确排序。在</p>
<p>有关bug#2的更多信息:</p>
<p><code>build_permitted_subs</code>函数不能正常工作——特别是,如果它遇到一对可以分成两个组的对,这意味着这些组也应该结合在一起,这就不会发生,现在会有两个组不应该分开。这会导致z重复,因为两个组都可以从z轴绘制。我已经用一个标志和一个追溯for循环草率地修复了这个问题。在</p>