Building a list - why is this code inefficient?

Question

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)

• Flambino: A 2200x speedup... not bad :)
• RubberDuck: Please do not update the code in your question after people have answered. This meta post explains why.
• RubberDuck: No problem. You're also welcome to join us in the chat room anytime.
• Cary Swoveland: How about: a = string.chars.sort; 1.upto(a.size) { |i| a.combination(i).each { |c| puts c.join } }?

Answer 1

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.

• niftygrifty: Awesome answer. Thanks! I added the code I ended up with to the original question.

Answer 2

Just a real small note. I don't like the variable l for a few reasons.

1. It's one letter. Go ahead and try to do a find & replace on that in your text editor. I dare you.

2. Variable names should be meaningful. Always. If anything, you could call it len. That's meaningful.

3. This code doesn't need it to be a variable. You could just call .size directly on the string that you stored already. That would be crystal clear to Mr. Maintainer.

   string = "bcdefghij"
   result = []
   permutations = string.split('').permutation.to_a
   string.size.times do
    permutations.each {|p| result << p.sort.join}
    permutations.map! {|p| p[1..-1]}
   end
   

I would think your performance issues comes from the nested loops. Remember, each and map are both loops. So what really happens is:

For each character in string

Loop through each permutation

Then Loop through each permutation again.

I would look for a way to reduce the number of loops. @Nat's answer seemed to have some good advice on how to accomplish that.

Ok, so that wasn't such a small note. I meant it to be. I swear.