找到序列排列的算法

我在問一個簡單的問題：如何在複雜度最低的數字序列（帶重複）中找到一個（且只有一個）排列？找到序列排列的算法

假設我們有序列：1 1 2 3 4。然後我們排列2和3，所以我們有：1 1 3 2 4。我怎麼能發現2和3已經被排列？最糟糕的解決方案是生成所有可能性，並將每一個與原始置換序列進行比較，但我需要一些快速的...

謝謝你的回答。

2012-11-07 Greg

我坦率地不明白這個問題。您是否在尋找從序列1到序列2所需的最少互換？ – st0le

您可以比較元素本身和元素的數量是否相同。 –

生成您想要檢測的所有排列（在您的示例中只有8個IICC）併爲其生成DFA。（f）lex是你的朋友。 – wildplasser

function findswaps: 
    linkedlist old <- store old string in linkedlist 
    linkedlist new <- store new string in linkedlist 

    compare elements one by one: 
     if same 
      next iteration until exhausted 
     else 
      remember old item 
      iterate through future `new` elements one by one: 
       if old item is found 
        report its position in new list 
       else 
        error

我卑微的嘗試，如果錯了，請糾正我，所以我可以幫助更好。我猜數據是無序的，所以它不能比線性更快？

來源

2012-11-07 10:04:21 Angad

與此問題是會有多個解決方案，您的問題沒有一些限制，如順序找到順序。

我想看的第一個測試是序列中仍然存在相同的值，如果是這樣，只需逐個逐個找到，直到發現不匹配，然後找到第一個出現的位置，標記爲置換。現在繼續搜索下一個修改，等等......

如果你只是想知道它有多少改變，我會看看levenshtein算法。這個算法的基礎甚至可以給你你自己的定製算法所需要的東西，或者激發其他方法。

這很快，但它不會告訴你哪些項目已經改變。

我所知道的唯一完整解決方案就是記錄每次更改的發生情況，以便查看更改的歷史記錄以瞭解最佳答案。

來源

2012-11-07 10:05:55 sradforth

如果只有1原始和派生陣列之間的交換，你可以嘗試在O（n）的像這樣的數組長度n：

int count = 0; 
int[] mismatches; 

foreach index in array { 
    if original[index] != derived[index] { 
     if count == 2 { 
      fail 
     } 
     mismatches[count++] = index; 
    } 
} 

if count == 2 and 
    original[mismatches[0]] == derived[mismatches[1]] and 
     original[mismatches[1]] == derived[mismatches[0]] { 

    succeed 
} 

fail

注意，這個報告的時候什麼也沒有換一個失敗陣列之間。

來源

2012-11-07 11:41:05 rsp

找到序列排列的算法

回答

相關問題