Building a list - why is this code inefficient?

I'm attempting this code challenge.

Here's my code modified to handle one simple example test case:

string = "bcdefghij"
l = string.size

result = []

permutations = string.split('').permutation.to_a

l.times do
  permutations.each {|p| result << p.sort.join}
  permutations.map! {|p| p[1..-1]}
end

puts result.uniq.sort

It produces the correct result but it's way too slow. I've played around with benchmarking and it looks like the slowest part of the code is this line:

permutations.each {|p| result << p.sort.join}

Can I speed this code up somehow? Or am I thinking about the original problem all wrong?

RESULT

Thanks to Nat's answer below I came up with this:

string = "bcdefghij".split('')
l = string.length

result = []
(1..l).each {|i| result += string.combination(i).to_a}
puts result.map{|r| r.join}.sort

Benchmarks

Before: 6.480000 0.310000 6.790000 ( 6.794669)

After: 0.000000 0.000000 0.000000 ( 0.003087)

It's inefficient because you're doing a lot of work to create a factorial l, iterating over it l times, each time REDOING all the work of sorting and joining each permutation, and then throwing away most of the results!

Here are some suggestions:

• You don't need to extend permutations into an array in memory (loose the to_a), a generator is generally more efficient to iterate over.

• You don't need to sort and join the permutations again for every length, this is probably the biggest waste of time. Once they've been sorted and joined you can uniqify them then and then create shorter strings from them (which will need uniqifying again but this will be less work).

• Finally, if instead you split and sort the input string at the beginning then you can use the combination function to generate only valid combinations for each length.

StackExchange Code Review Q#55839, answer score: 4