Генерация перестановок итеративно без рекурсии или стека с Ruby / Erlang

Question

Я хотел бы сгенерировать все перестановки списка, но я бы хотел отфильтровать некоторые перестановки, прежде чем они будут добавлены в стек или сохранены где-либо.

Я отфильтрую перестановки на основе некоторых пользовательских специальных правил.

Другими словами, я хотел бы создать список перестановок большого списка (50-300 элементов), но я хотел бы выбросить большинство сгенерированных перестановок прямо во время процесса (я знаю, чтополное число перестановок N!).

Я пробовал Ruby с его Array.permutation.to_a, но похоже, что он поддерживает полный стек во время выполнения, поэтому у меня закончилась память (8 ГБ) довольнобыстро.

Я также пробовал это решение Erlang, но, похоже, оно работает аналогично предыдущему Ruby.

Есть ли какие-либо нестандартные решения этой проблемы?

PS Я прочитал это и это , но, к сожалению, я не знаю C / C ++.

Answer 1

Ruby's Array.permutation.to_a действительно создает массив.Не используйте to_a тогда!Это означает «массив».Array.permutation дает вам «перечислитель», генератор.Поскольку вы хотите отбросить большинство перестановок, используйте reject.

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!есть