How to find all permutations of an Array of Strings in Ruby without using too much memory?

Question

line = gets
L=line.split(" ")

searchMap=L.permutation.map(&:join)
S =  gets

searchMap.each do |item|
    if S.include? item
        puts S.index(item)
        end
end

If L is very large then I get `join': failed to allocate from permutation from each.

Some programming hints... Don't use `L` and `S` as variable names; local, @instance, and @@class variables are snake_case, which means `search_map` would be the correct case and spelling. Constants start with Upper-case and have different scope. These are idiomatic in Ruby, based on how the language works. — the Tin Man, Sep 24 '13 at 13:39
Also, as a practice, you probably always want to use `gets.chomp` instead of `gets` by itself. Reading user input from the console will return an invisible trailing carriage-return+line-feed or just a line-feed, depending on the OS. In either case it's a trap for the unwary that we regularly see here. — the Tin Man, Sep 24 '13 at 13:46

score 2 · Accepted Answer · edited Sep 24 '13 at 13:49

What you're doing now is creating an enumerator which will yield one permutation at a time, not consuming much memory, then with the .map(&:join) you're putting everything that comes out of this enumerator into one gigantic array searchMap.

Instead of that you should pull one permutation from the enumerator at a time and do your trick on that, instead of iterating over the gigantic array with searchMap.each:

line = gets
L=line.split(" ")

S =  gets

L.permutation do |item|
    if S.include? item.join
        puts S.index(item.join)
    end
end

score 1 · Answer 2 · edited May 23 '17 at 11:56

1

You can calculate each permutation without computing others, check out this question "Finding n-th permutation without computing others" and you will find the answer in C.

edited May 23 '17 at 11:56

Community

1
1

answered Sep 24 '13 at 13:23

Ricky Bobby

7,490
7
46
63

How to find all permutations of an Array of Strings in Ruby without using too much memory?

2 Answers2