如何有效地存储一大组排列？

比方说，我们有元素的列表：如何有效地存储一大组排列？

[{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

如何有效地存储一大组排列？

回答

相关问题