如何有效地存儲一大組排列？

比方說，我們有元素的列表：如何有效地存儲一大組排列？

[{dog,1},{dog,2},{cat,1},{cat,2},{bird,1},{bird,2},...]

我想用來存儲該列表在RAM中的所有可能permutations。

由於列表可能相當長（10個元素或更多），因此需要很大的空間來存儲它（因子N）。例如，如果我有一個列表，其中包含約70個字節的空間，並且有12個元素，那麼我需要12! * 70 ~ 31 GB。如果我只在列表中添加一個元素，那麼將這些排列存儲在RAM中可能變得不可行。

是否有任何更有效的表示形式來保存內存中的所有排列比以下Erlang表示？

[{dog,1},{dog,2},{cat,1},{cat,2},{bird,1},{bird,2},...]

（我知道原子dog只存儲一次在原子表，但因爲它在每個排列重複，需要N個存儲器）。

也許這些排列可能存儲在某種字節表示中？ （對不起，我是一個字節和二進制文件的新手）。

畢竟，它只是相同的元素，但以不同的方式重新排列。

來源

2012-01-03 skanatek

爲什麼不生產他們懶惰？從每個列表中保留一個索引，當被問及一個新的元素時，您即時生成組合。這樣，您只需要隨時將初始源元素列表存儲在內存和索引中。

例如（如果你需要遍歷排列）：

-record(perm, {list_a, list_b, index_a, index_b}).

每當你達到最大的index_b，你把它重置爲0，並用一個遞增index_a。然後，訪問列表的第N個元素（其中N是索引），您可以重新創建任何排列實例。

當然，這意味着每次產生排列時都必須遍歷列表。爲了避免這種情況，你可以使用列表作爲指數本身：

-record(perm2, {list_a, list_b, list_b_orig}).

以產生下一個排列，從list_b流行的新元素和它添加到list_a頭。如果list_b爲空，則刪除list_a的頭部，並通過將list_b設置爲保存在list_b_orig中的原件重新開始。

來源

2012-01-04 09:01:58

亞當，請您提供您的答案的詳細信息？憑藉我有限的知識，我只理解我應該有一個（DB？矩陣？）表，它具有行中的所有唯一列表元素和列中的所有排列。相應的單元格應該存儲特定列表（排列）中特定元素的確切索引（地點編號）。我相信你的答案意味着更優雅的解決方案。 – skanatek 2012-01-04 10:44:23

查看更新後的帖子。關鍵是不要一次完全創建所有的排列。 – 2012-01-04 14:24:31

對不起，成爲這樣的新手，但我不明白我應該如何使用您提供的記錄結構。我應該在list_a和list_b中存儲什麼？ Erlang列表數據類型的index_a和index_b或其他什麼？ – skanatek 2012-01-04 16:14:46

也許壓縮它會做的工作？

Zlib模塊似乎做了這樣的事情。

來源

2012-01-04 07:50:28

如果您有N個元素的列表，則有N！排列。所以如果我們能夠產生從數字1到N的映射！（或0到N！-1）以可重現的方式排列到這些排列，我們不需要存儲N！元素列表，但只有N！數字。

但停止 - 我們爲什麼要存儲N！號碼？我們不需要存儲它們，因爲它們不會改變。我們只需要上限，它由最大元素索引定義，即N，它應該已經存儲在您的代碼中。

對不起，不知道Erlang，但I wrote a functional algorithm in Scala，它允許以可重現的方式產生任意大小的排列。例如，數字（1至12）的排列是123456790列表（4,2,1,5,12,7,10,8,11,9,3,6）。

作爲一項特別的獎勵，此算法以排序的方式生成排列。只需以可複製的方式查找所有排列但無需訂單更簡單：

def permutationIndex (idx: Int, list: List [Int]) : List [Int] = { 
    if (list.isEmpty) list else { 
    val el = list (idx % list.size) 
    el :: permutationIndex (idx/list.size, list.remove (_ == el))}}

來源

2012-01-23 09:31:54

如何有效地存儲一大組排列？

回答

相關問題