採訪準備：優化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來達到。

如果您有任何問題或任何不能解決的問題，請告訴我，我將開始詳細說明/調試。 （截至格林威治標準時間19:28，我已經注意到一個錯誤並將其編輯出來）。錯誤＃2（在測試用例3中有重複的z）也應該修復。

多了幾分錯誤＃1：

我沒有排序由build_permitted_subs返回的指標，所以無法正確它們參照排序，swap_str。

更多的bug＃2：

的build_permitted_subs功能不能正常工作 - 特別是，如果遇到一對能去成兩個組，這意味着這些羣體也應聯合起來，這並沒有發生，現在有兩組不應該分開。這會導致z複製，因爲兩個組都可以從z中抽取。我用一個標誌和追溯循環來修復這個問題。

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