面试准备:优化swapLexOrder

Question

采访哈希地图问题的代码战斗，需要帮助优化我的蛮力解决方案。以下是问题所在：

给定字符串str和指示字符串中哪些索引可以交换的对数组，则返回因执行允许的交换而产生的按字母顺序排列的最大字符串。您可以任意次数交换索引。

示例

For str = "abdc" and pairs = [[1, 4], [3, 4]], the output should be
swapLexOrder(str, pairs) = "dbca".

通过交换给定的索引，可以得到字符串："cbda“、"cbad”、"dbac“、"dbca”。该列表中按字母顺序排列的最大字符串是"dbca“。

我的当前解决方案

暴力不断增加所有可能性，直到没有新的解决方案。这对swapLexOrder('dznsxamwoj',[[1,2],[3,4],[6,5],[8,10]])来说太慢了，不能在我的机器上完成。有优化的提示吗？通过的一个更简单的测试用例是swapLexOrder('abdc,[[1,4],[3,4]])= dbca

def swapLexOrder(str, pairs):
    d = {}
    d[str]=True
    while True:
        oldlen=len(d)
        for x,y in pairs:
            for s in d.keys():
                d[swp(s,x,y)]=True
        if len(d) == oldlen:
            #no more new combinations.
            return sorted(d)[-1]

def swp(str,x,y):
    x=x-1
    y=y-1
    a=str[x]
    b=str[y]
    return str[0:x]+b+str[x+1:y]+a+str[y+1:]

Answer 1

我建议的解决方案是首先尝试“链接”尽可能多的对，以形成一组可以互换的索引--例如在您的第一个示例中，[[1, 4], [3, 4]]可以成为[[1, 3, 4]]。然后，这些索引的每一个子集都可以按字典顺序排序，形成输出。执行情况如下：

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]]))

产出：

zdsnxamwoj
dbca
zdxrabca

我还将您的参数重命名为不使用str，这已经是一个非常基本的Python内置程序。请注意，我的代码可能不是尽可能的Pythonic，但我认为它的工作能力足以说明该算法，而且它没有受到任何主要性能影响。我怀疑这种方法的复杂度很低--它通常是“智能的”，因为它不强暴任何东西，并且使用O(n log n)排序。第一个例子似乎是正确的。请注意，这会将每对转换为基于0的，因为这对于Python来说要容易得多。

这在一定程度上依赖于能够从相邻的排列(交换对)中形成任何排列(排序链接对)。这可能不是完全直观的，但它可能会帮助您认识到，您可以使用列表中的相邻交换来有效地执行插入(通过不断地在元素的方向上交换元素)。使用相邻的交换排列列表的一个例子是气泡排序，您可能会意识到，如果任何置换都可以通过bubblesort实现，那就意味着所有的置换都可以通过bubblesort实现。

如果您有任何问题，或者任何事情不起作用，请告诉我，我将开始详细说明/调试。(截至格林尼治时间19:28时，我已经注意到了一个bug，并将其编辑出来：)。Bug #2 (在测试用例3中有重复的z)也应该修复。

更多关于bug #1的内容：

我没有对build_permitted_subs返回的索引进行排序，因此它无法参照swap_str正确地对它们进行排序。

关于bug #2的更多信息：

build_permitted_subs函数没有正常工作--特别是，如果它遇到了一个可以分成两个组的组，这意味着这些组也应该连接在一起，这是没有发生的，现在有两个组不应该分开。这将导致z复制，因为这两个组都可以从z中提取。我已经草率地用一个标志和一个追溯的for循环修复了这个问题。

Answer 2

这个也许更好用。

def swapLexOrder(str_, pairs):
n = len(str_)
str_ = list(str_)

corr = [set() for _ in range(n)]
nodes = set()
for a, b in pairs:
    corr[a-1].add(b-1)
    corr[b-1].add(a-1)
    nodes.add(a-1)
    nodes.add(b-1)

while nodes:
    active = {nodes.pop()}
    group = set()
    while active:
        group |= active
        nodes -= active
        active = {y for x in active for y in corr[x] if y in nodes}

    chars = iter(sorted((str_[i] for i in group), reverse=True))
    for i in sorted(group):
        str_[i] = next(chars)

return "".join(str_)

Answer 3

def swapLexOrder(str, pairs):
    
    if not str or not pairs:
        return ('', str)[not pairs]
    lst = [''] + list(str)
    setted_pairs = list(map(set, pairs))
    while setted_pairs:
        path = setted_pairs.pop(0)
        while True:
            path1 = path.copy()
            for pair in setted_pairs:
                if path1 & pair:
                    path |= pair
                    setted_pairs.remove(pair)
            if path == path1:
                break
        optimal = sorted(lst[i] for i in path)
        for i, v in enumerate(sorted(path, reverse=True)):
            lst[v] = optimal[i]
    return ''.join(lst[1:])