Module: Enumerable
- Defined in:
- lib/tsplab.rb
Overview
Enumerable
The code for the Traveling Salesman lab (tsplab.rb) extends the Enumerable module with a method that generates all permutations of a string, array, or any other object from a class the includes the Enumerable interface.
Instance Method Summary collapse
-
#each_permutation ⇒ Object
Iterate over all possible permutations of the objects in this container.
Instance Method Details
#each_permutation ⇒ Object
Iterate over all possible permutations of the objects in this container. The permutations are generated in lexicographic order.
Example:
>> s = "ABCD"
=> "ABCD"
>> s.each_permutation { |x| p x }
"ABCD"
"ABDC"
"ACBD"
"ACDB"
"ADBC"
...
"DBCA"
"DCAB"
"DCBA"
=> nil
1277 1278 1279 1280 1281 1282 1283 1284 1285 1286 1287 1288 1289 1290 1291 1292 1293 1294 1295 1296 1297 1298 1299 1300 1301 1302 1303 1304 1305 1306 1307 |
# File 'lib/tsplab.rb', line 1277 def each_permutation p = self.clone n = p.length res = [] loop do if block_given? yield p else res << p.clone end # find largest j s.t. path[j] < path[j+1] j = n-2 while j >= 0 break if p[j] < p[j+1] j -= 1 end break if j < 0 # find largest i s.t. path[j] < path[i] i = n-1 loop do break if p[j] < p[i] i -= 1 end # exchange path[j], path[i] p[j], p[i] = p[i], p[j] # reverse path from j+1 to end tmp = p.slice!(j+1, n-1) p += tmp.reverse end return block_given? ? nil : res end |