生成一些數字範圍的所有排列序列

給出以下算法，我們應該用java寫出它。然而，當我試圖理解逐行，它就會混亂，特別是部分：生成一些數字範圍的所有排列序列

A [K + 1：N-1] =升序S中的值

要據我瞭解，該套裝隨時只有1個號碼。我們怎樣才能取代A[k+1:N-1]當集只有1個號碼？

設A是一個整數序列0到N-1按升序排列（假設它是一個數組int[N]）。

next_permutation(A): 
    k = N-1 
    S = { } 
    while k >= 0: 
     if S contains a value larger than A[k]: 
      v = the smallest member of S that is larger than A[k] 
      remove v from S 
      insert A[k] in S 
      A[k] = v 
      A[k+1:N-1] = the values in S in ascending order. 
      return true 
     else: 
      insert A[k] in S 
      k -= 1 
    return false

來源

2013-10-17 Iann Wu

爲什麼你認爲S總是包含一個數字？ – templatetypedef

讓我們假設N是4. 它從無到始，因此第一個循環將向該集合添加3。第二個循環將取代3乘2，然後如此。 –

但是如果A [k]中的值小於A [k-1]？在這種情況下，在第一次迭代A [k]被添加並且k被設置爲k-1。然後在第二次迭代中，S不包含大於A [k]的任何東西（因爲k不同），所以另一個元素被添加。 – templatetypedef

顯示的算法類似於Generation in lexicographic order。您可以閱讀文章以獲取更多信息。

@templatetypedef關於如何以集合中的值升序排列數組中的項目的任何線索？例如A [k + 1：N-1] = S中的值按升序排列。我應該使用toArray（）嗎？

這是不需要的。您可以嘗試保持S數組始終排序。每當你想在數組中插入一個新數字時，你都會插入一個新的數字，所以數組可以保持排序。例如，如果您有S = [5 7 8]到目前爲止，並且您想要插入6，則插入5和7之間 - S = [5 6 7 8]。這樣，替換步驟就是將元素從S複製到A [k + 1：N-1]。

來源

2013-11-15 08:40:31 rado

生成一些數字範圍的所有排列序列

回答

相關問題