Generate permutations iteratively without recursion or stack with Ruby/Erlang

Question

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.

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!).

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.

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?

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

Answer 1

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

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?