使用 Ruby/Erlang 迭代生成排列，无需递归或堆栈 [英] Generate permutations iteratively without recursion or stack with Ruby/Erlang

问题描述

我想生成列表的所有排列，但我想在将某些排列添加到堆栈或存储在任何地方之前过滤掉它们.

I would like to generate all permutations of a list, but I would like to filter out some of the permutations before they are added to the stack or stored anywhere.

我将根据一些自定义的临时规则过滤掉排列.

I will filter out the permutations based on some custom ad-hoc rules.

换句话说，我想生成一个大列表(50-300 个元素)的排列列表，但我想在此过程中丢弃大部分生成的排列(我知道完整的数字的排列是 N!).

In other words, I would like to generate a list of permutations of a large list (50-300 elements), but I would like to throw out most of the generated permutations right during the process (I know that the full number of permutations is N!).

我已经尝试使用 Ruby 及其 Array.permutation.to_a，但它看起来在执行过程中维护了一个完整的堆栈，所以我很快就耗尽了内存 (8 GB).

I have tried Ruby with its Array.permutation.to_a, but it looks like it maintains a full stack during execution, so I ran out of memory (8 GB) fairly quickly.

我也尝试过 this Erlang 解决方案，但它似乎执行类似于以前红宝石一号.

I have also tried this Erlang solution, but it seems to perform similar to the previous Ruby one.

这个问题有什么定制的解决方案吗?

Are there any custom solutions to this problem?

附:我已阅读 this 和 this，但不幸的是我不懂 C/C++.

P.S. I have read this and this, but unfortunately I do not know C/C++.

推荐答案

Ruby 的 Array.permutation.to_a 确实产生了一个数组.那就不要使用 to_a 了！它的意思是排列".Array.permutation 给你一个枚举器"，一个生成器.由于您想丢弃大多数排列，请在其上使用 reject.

Ruby's Array.permutation.to_a does indeed produce an array. Don't use to_a then! It means 'to array'. Array.permutation gives you an 'enumerator', a generator. Since you want to throw out most permutations, use reject on it.

res = [1,2,3,4].permutation(3).reject do |perm|
  perm.first.even? #if this line is true, the perm will be rejected
end

将生成三个元素的所有排列，并拒绝第一个位置为偶数的那些.但是嗯……你见过多少300！是吗?

will generate all permutations of three elements and reject those with an even number on the first position. But ehm... have you seen how much 300! is?

这篇关于使用 Ruby/Erlang 迭代生成排列，无需递归或堆栈的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！