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

Question

假设我们有一个元素列表:

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

我想存储所有可能的 permutations RAM 中的此列表。

由于列表可能很长(10 个元素或更多)，因此需要大量空间来存储它(阶乘 N)。

例如，如果我有一个列表，它占用大约 70 个字节的空间并包含 12 个元素，那么我需要 12! * 70 ~ 31 GB。如果我再向列表中添加一个元素，则可能无法将排列存储在 RAM 中。

是否有比以下 Erlang 表示更有效的表示来将所有排列保留在内存中？

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

(我知道原子 dog 在 atoms 表中只存储了一次，但由于它在每次排列中重复出现，因此它占用 N 内存)。

也许这些排列可以存储在某种字节表示中？ (抱歉，我是字节和二进制文件的新手)。

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

Answer 1

为什么不懒惰地生产它们？从每个列表中保留一个索引，当被要求添加新元素时，您可以即时生成组合。这样，您只需随时将源元素的初始列表和索引存储在内存中。

例如(如果您需要遍历排列):

-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 。