（任何語言）使用交換查找矢量中元素的所有排列

今天在實驗室會議中，我被問到了這個問題。（任何語言）使用交換查找矢量中元素的所有排列

我們可以想象一個包含元素1 ... N-1，長度爲N的向量。是否有一個算法（系統）方法來生成向量中所有元素的排列或順序。一種提議的方法是交換隨機元素。顯然，如果以前生成的所有排列都存儲起來以備將來參考，那麼這將工作，但這顯然是一種非常低效的方法，無論是在空間上還是在時間上都是明智的。

這樣做的原因是從矢量中的特殊位置移除特殊元素（例如零的元素），其中不允許這樣的元素。因此，隨機方法並不是很荒謬，但想象一下這樣一種情況，即元素的數量很大，可能的排列的數量（在任何「特殊位置」都沒有「特殊元素」）是低。

我們試圖通過這個問題工作爲N的情況下= 5：

x = [1, 2, 3, 4, 5]

首先，交換元件4和5：

x = [1, 2, 3, 5, 4]

然後交換3和5：

x = [1, 2, 4, 5, 3]

然後3和4：

x = [1, 2, 5, 4, 3]

最初我們認爲使用兩個索引ix和jx可能是一個可能的解決方案。喜歡的東西：

ix = 0; 
jx = 0; 

for(;;) 
{ 
    ++ ix; 

    if(ix >= N) 
    { 
     ix = 0; 
     ++ jx; 

     if(jx >= N) 
     { 
      break; // We have got to an exit condition, but HAVENT got all permutations 
     } 
    } 

    swap elements at positions ix and jx 

    print out the elements 
}

這適用於其中N = 3，但是它並不適用於更高的工作N.我們認爲，這種做法可能是沿着正確的線的情況。我們試圖擴展到使用3個索引的方法，出於某種原因，我們認爲這可能是解決方案：使用第三個索引標記索引ix開始或結束的向量中的位置。但是我們陷入了困境，並決定向SO社區尋求建議。要做到這一點

來源

2013-11-28 user3728501

請參閱http://stackoverflow.com/questions/12256824/how-to-increase-memory-to-handle-super-large-lua-tables/12267647#12267647。 – lhf

對於C++，總是存在std :: next_permutation（按照字典順序排列，沒有交換） –

的一種方法是，第一個字符e：

下一個元素上首先遞歸
然後，對每個元素e2e後：
- 交換e和e2
- 然後遞歸下一個元素
- 並撤銷swap

僞代碼：

permutation(input, 0) 

permutation(char[] array, int start) 
    if (start == array.length) 
     print array 

    for (int i = start; i < array.length; i++) 
     swap(array[start], array[i]) 
     permutation(array, start+1) 
     swap(array[start], array[i])

使用該功能的主要電話時，它會嘗試在第一位置的每個字符，然後遞歸。簡單地循環所有的字符在這裏工作，因爲我們之後撤消每個交換，所以在遞歸調用返回後，我們保證回到我們開始的位置。

然後，對於每個遞歸調用，它會嘗試每個剩餘的字符在第二個位置。等等。

Java live demo。

來源

2013-11-28 18:27:20 Dukeling

（任何語言）使用交換查找矢量中元素的所有排列

回答

相關問題