Help with Permutation

1

I’m using the Ruby permutation method on the digits (0…9) taken n at a time, for n determined when called. I can easily skip using the next permutation for further computation for each one that begins with a pre-specified digit, for example
no = 3
(0…9).to_a.permutation(4).each do |numbers|
next if numbers[0] == no
…
But I’d like that to go immediately to numbers[0] = no+1. Is there any way I can arrange this?

2

Unfortunately I don’t think it’s possible, because the permutation() method returns an Enumerator. You can omit the .each() and still pass a block on permutation(). To be able to do such stuff with maximum performance, you may need to have your own implementation of permutation which skips the recursion/loop on the condition numbers[0] == no. In that case, you don’t have an array of that number at all. But I don’t have any idea if it can go straight to numbers[0] == no with time complexity O(1).

The bigger problem is, if you write such method in pure Ruby, it will probably be even slower than the Ruby’s permutation and going over each item, because that one is written in C. So for now, your best idea would be to use the existing code. Or maybe you can use this:

no = 3

ary = (0...9).to_a.permutation(4).find { |numbers|
	numbers[0] != no
}

Or to select all items:

no = 3

arys = (0...9).to_a.permutation(4).select { |numbers|
	numbers[0] != no
}

For me, the find is instant with 0..200, but it takes a couple of seconds when I change it to n = 3 to n = 0. This doesn’t use any more memory than 0...9, but it takes more CPU time for sure.

1 Like
3

Thanks. I might try to use the select approach and process only selected permutations–it probably isn’t any faster, but I like the way it looks better.

1 Like
4

I forgot, you can also use .reject:

no = 3

arys = (0...9).to_a.permutation(4).reject { |numbers| numbers[0] == no }

It rejects if numbers[0] is no. All of these are super slow. There probably isn’t much way without having to iterate over all the items. In C [ C Ruby Extension ], you can do this very fast. So maybe we can write a gem, but probably it won’t be worth it :smiley: