產生移位的記憶法

有什麼方法可以產生產生移位的記憶法。例如數字1234 ...產生移位的記憶法

對我來說，問題是它需要大量的內存。有沒有辦法在一些適量的內存中使用

來源

2011-12-19 Abdul Samad

你的意思是：如何*列舉*排列？ – wildplasser 2011-12-19 16:31:25

對於任何字符串，用n個不同的字符表示，n！存在排列，因此需要的空間將很大。如果你只需要枚舉排列，那麼我會建議不要存儲它們，但直接顯示每一個，因爲你計算每一個

來源

2011-12-19 16:54:28 TimeToCodeTheRoad

如果我不存儲它們，只是顯示，然後每次我必須重新計算我已經計算的東西..... – 2011-12-19 17:04:06

是的，當然，有可能使用memoization產生排列（幾乎任何其他計算，當它是有意義的）。具體的步驟取決於你的排列生成算法。例如，如果函數perms(numbers)採用一組數字（例如，{1, 2, 3, 4}）並通過遞歸調用perms()返回所有置換（這些數字的有序向量，例如{[1, 2, 3, 4], [1, 2, 4, 3], [1, 3, 2, 4], ...}）的集合，其子集爲numbers，則可以記憶此perms()函數直。爲此，請將緩存創建爲映射，其中鍵是數字集合，值是函數調用的結果。

關於你的問題的第二部分（關於記憶）。記憶本身使用大量的記憶。您始終可以通過使用某種固定大小的緩存（例如LRU/LFU地圖）來修復此金額，但您應該明白，這會打破記憶概念，並且一些對perms()的調用仍將被計算兩次或更多次。

來源

2011-12-19 17:42:17 ffriend

我明白了你的觀點，但我認爲使用地圖的想法不是很好，因爲地圖傳說lgn（對數）時間來檢索具有給定鍵的元素。 – 2011-12-19 21:45:17

@AbdulSamad：Map是抽象數據類型，例如它可以實現爲HashMap，因此可以分解爲O（1）（常量時間）。即使在實現樹的情況下，對於大多數perms（）調用來說，它仍然會更快。 – ffriend 2011-12-20 02:05:12

如果您想要連續生成排列並且不需要它們全部同時完成，那麼按照詞典順序遍歷它們可能會更好。編寫一個函數nextPerm，它接受一個置換並返回next permutation in lexicographic order。

來源

2011-12-19 18:26:08 PengOne

產生移位的記憶法

回答

相關問題