使用亞線性內存生成排列

我想知道是否有足夠簡單的算法來生成N個元素的排列，例如1..N，它使用的內存少於O(N)。它不必計算第n個排列，但它必須能夠計算所有排列。使用亞線性內存生成排列

當然，這種算法應該是某種類型的發電機，或使用其使用小於O(N)存儲器中，由於返回結果作爲尺寸N的向量已經違反了子線性存儲器限制一些內部數據結構。

來源

2011-11-07 eold

的條款，除非元素有一個已經預先定義爲了他們，如整型，這樣你可以產生下一個需要的時候，就不會只是接受元素作爲輸入的N多已經把你O（N）內存限制？ – Wizetux

會，這就是爲什麼我說的元素are' 1..N'，使他們不必爲輸入向量傳遞。 – eold

這個怎麼樣？ O（1）在空間中，但運行時可能是無界的：'Random rnd = ...;列表 l = ...; while（l.size（）

我認爲答案必須是「否」。

將N元排列的生成器看作一個狀態機：它必須至少包含與排列相同的狀態，否則它將在完成全部生成之前開始重複。

有N！這樣的排列，這將需要至少ceil（log2（N！））位來表示。 Stirling's approximation告訴我們log2（N！）是O（N log N），所以我們將無法用亞線性內存創建這樣一個生成器。

來源

2011-11-07 23:53:42 comingstorm

True。但是有可能用O（N）存儲器產生一個隨機置換。分佈應該是一致的，否則可以總是產生1..N，這是一個有效的排列？ – eold

爲了生成有效的排列，您需要一些方法來「記住」已生成的元素，這樣可以避免重複它們。您可以通過保留您的初始僞隨機數字生成器狀態的副本，併爲每個生成的元素重新運行它來拒絕重複的元素。這將減少對O（log N）位（存儲當前目標索引）的內存需求加上生成器狀態的大小。但是，此方法的運行時間至少爲O（N^2），並且O（N^2 log N）的平均情況（由於以後元素的許多重試）。 – comingstorm

注意：如果僞隨機數發生器狀態的大小小於排列數，則永遠不會生成某些排列。然而，一個體面的PRNG應該分發它廣泛產生的排列，並且沒有一個容易辨別的模式......在實踐中，這應該不成問題。 – comingstorm

我們假設一次產生一個條目的隨機排列。發生器的狀態必須對剩餘的元素集進行編碼（運行完成），因此，由於不可能排除任何可能性，因此發生器狀態至少爲n位。

來源

2011-11-07 23:53:59

由於有一個使用n + O（log n）位的生成器，所以這個界限基本上很緊密。 –

好點。但是如果我對隨機置換感興趣，並且具有一致的概率分佈？ – eold

的C++算法next_permutation執行序列的就地重排成其下排列，或當沒有進一步的排列存在返回false。該算法如下：

template <class BidirectionalIterator> 
bool next_permutation(BidirectionalIterator first, BidirectionalIterator last) { 
    if (first == last) return false; // False for empty ranges. 
    BidirectionalIterator i = first; 
    ++i; 
    if (i == last) return false; // False for single-element ranges. 
    i = last; 
    --i; 
    for(;;) { 
     BidirectionalIterator ii = i--; 
     // Find an element *n < *(n + 1). 
     if (*i <*ii) { 
      BidirectionalIterator j = last; 
      // Find the last *m >= *n. 
      while (!(*i < *--j)) {} 
      // Swap *n and *m, and reverse from m to the end. 
      iter_swap(i, j); 
      reverse(ii, last); 
      return true; 
     } 
     // No n was found. 
     if (i == first) { 
      // Reverse the sequence to its original order. 
      reverse(first, last); 
      return false; 
     } 
    } 
}

這使用對於生成的每個置換恆定空間（迭代）。你認爲這是線性的嗎？

來源

2011-11-07 23:54:11

我認爲，即使存儲你的結果（這將是一個有序的N項列表）將在內存中爲O（N），不是嗎？無論如何，爲了回答你隨後關於隨機挑選一個置換的問題，這裏有一種技術，比只產生所有N更好！列表中的可能性，然後隨機選取一個索引。如果我們可以隨機選擇索引並從中生成相關的排列，那麼我們就好多了。

我們可以根據單詞/排列在詞典中出現的順序，想象出單詞/排列的字典順序，並將這些單詞與這些單詞相關聯。例如，在三個字符的話會

perm.    index 
    012 <---->  0 
    021 <---->  1 
    102 <---->  2 
    120 <---->  3 
    201 <---->  4 
    210 <---->  5

以後你就會明白爲什麼這是最容易使用我們做的數字，但其他人可以容納帶着幾分更多的工作。

要隨機選擇一個，你可以從一個統一的概率範圍0 ... N！-1中隨機選擇一個相關的索引（對於即使是中等大小的N，最簡單的實現也是不成問題的，我知道，但我認爲有體面的解決方法），然後確定其相關的排列。注意，列表以所有最後N-1個元素的排列開始，保持第一個數字固定爲0.在這些可能性耗盡之後，我們生成所有以1開頭的數字。在這之後（N-1）！排列耗盡，我們生成以2開頭的那些。因此，我們可以確定前導數字是Floor [R /（N-1）！]，其中R是上面所示的索引。現在看看我們爲什麼零索引？

爲了生成在排列剩餘的N-1個數字，讓我們說，我們確定樓層[R /（N-1）！] = A0。從列表{0，...，N-1} - {a0}（設置減法）開始。我們想要這個列表的第Q個排列，對於Q = R mod（N-1）!.除了解釋數字缺失的事實，這與我們剛剛解決的問題一樣。遞歸。

來源

2011-11-08 04:12:51 josh

也許你可以與factoradic數字。您可以一步一步地從中提取出結果的排列，因此您不必將整個結果存儲在內存中。

但我開始也許原因是，我不知道是什麼factoradic號碼本身是規模不斷增長的行爲。如果在32位整數或類似的東西適應，N將被限制在一個恆定如此O（N）將等於O（1），所以我們必須使用數組，但我不能確定它是如何將大在N.

來源

2011-11-08 08:34:11 harold

使用亞線性內存生成排列

回答

相關問題