Generate substitutions iteratively without recursion or stack with Ruby / Erlang

Question

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

I will filter out permutations based on some ad hoc custom 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 directly during the process (I know that the total number of permutations is N! ).

I tried Ruby with my Array.permutation.to_a , but it looks like it supports a full stack at runtime, so I quickly ran out of memory (8 GB).

I also tried this Erlang solution, but it looks like it is similar to the previous Ruby.

Are there any individual solutions to this problem?

PS I read this and this , but unfortunately I do not know C / C ++.

Answer 1

Ruby Array.permutation.to_a really creates an array. Do not use to_a then! This means an array. Array.permutation gives you an "enumerator" 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 the three elements and reject those with an even number in the first position. But um ... you saw how many 300! this is?