Permutations/Rank of a permutation: Difference between revisions
→{{header|Ruby}}: Added Ruby Header and sample
(GP) |
(→{{header|Ruby}}: Added Ruby Header and sample) |
||
Line 883:
</pre>
=={{header|Ruby}}==
<lang ruby>class Permutation
include Enumerable
attr_reader :num_elements, :size
def initialize(num_elements)
@num_elements = num_elements
@pi = (0..num_elements-1).to_a
@size = fact(num_elements)
end
def each(upper=@size)
return self.to_enum unless block_given?
(0..@size-1).each{|i| yield unrank(i)}
end
def unrank(r) # nonrecursive version of Myrvold Ruskey unrank2 algorithm.
pi = @pi.dup
(@num_elements-1).downto(1) do |n|
s, r = r.divmod(fact(n))
pi[n], pi[s] = pi[s], pi[n]
end
pi
end
def rank( pi) # nonrecursive version of Myrvold Ruskey rank2 algorithm.
pi = pi.dup
pi1 = pi.zip(0...pi.size).sort.map(&:last)
(pi.size-1).downto(0).inject(0) do |memo,i|
s = pi[i]
pi[i], pi[pi1[i]] = pi[pi1[i]], pi[i]
pi1[s], pi1[i] = pi1[i], pi1[s]
memo += s * fact(i)
end
end
private
def fact(n)
return 1 if n.zero?
n.downto(1).inject(:*)
end
end
</lang>
Demo:
<lang ruby>puts "All permutations of 3 items from and back to rank."
perm = Permutation.new(3)
(0..perm.size-1).each{|num| puts "#{num} --> #{prm=perm.unrank(num)} --> #{perm.rank(prm)}"}
puts "\n4 random samples of 12 items:"
perm = Permutation.new(12)
4.times{ p perm.unrank(rand(perm.size))}
puts "\n4 random uniq samples of 144 items:"
perm, rands = Permutation.new(144), {}
# generate 1_000_000 unique random numbers in the range (0..144!) (takes about 2.5 seconds)
rands[rand(perm.size)] = true until rands.size == 1_000_000
random_perms = rands.keys.each.lazy{|k| perm.unrank(k)}
# random_perms is lazy. Generate permutations one by one:
4.times{p perm.unrank(random_perms.next)}
</lang>
{{out}}
<pre style="overflow:auto">
All permutations of 3 items from and back to rank.
0 --> [1, 2, 0] --> 0
1 --> [2, 1, 0] --> 1
2 --> [2, 0, 1] --> 2
3 --> [0, 2, 1] --> 3
4 --> [1, 0, 2] --> 4
5 --> [0, 1, 2] --> 5
4 random samples of 12 items:
[9, 6, 3, 11, 8, 7, 10, 0, 1, 4, 2, 5]
[5, 1, 0, 9, 6, 4, 3, 2, 7, 11, 10, 8]
[3, 9, 5, 7, 10, 1, 11, 6, 8, 2, 4, 0]
[0, 7, 3, 4, 6, 9, 5, 2, 11, 1, 10, 8]
4 random uniq samples of 144 items:
[12, 130, 62, 35, 60, 95, 2, 31, 54, 61, 51, 18, 48, 118, 32, 124, 17, 9, 122, 10, 86, 137, 24, 90, 57, 138, 120, 94, 53, 3, 40, 15, 69, 11, 22, 134, 87, 143, 115, 8, 129, 49, 43, 50, 97, 16, 41, 127, 93, 119, 73, 6, 65, 106, 55, 100, 88, 42, 64, 5, 121, 77, 131, 72, 126, 113, 78, 0, 46, 68, 39, 76, 116, 34, 107, 110, 139, 26, 83, 38, 141, 80, 56, 84, 23, 142, 111, 75, 82, 103, 70, 21, 123, 66, 104, 96, 27, 135, 33, 1, 140, 37, 81, 105, 112, 132, 102, 92, 14, 136, 91, 20, 7, 13, 25, 59, 36, 133, 79, 19, 63, 45, 28, 67, 109, 85, 108, 114, 44, 128, 99, 101, 4, 89, 117, 47, 29, 52, 98, 74, 30, 125, 58, 71]
[5, 63, 10, 18, 125, 39, 36, 100, 8, 41, 37, 7, 78, 88, 111, 6, 89, 13, 25, 137, 126, 95, 59, 11, 128, 123, 46, 94, 124, 1, 135, 38, 29, 62, 68, 61, 52, 21, 134, 75, 93, 42, 132, 104, 87, 22, 64, 14, 74, 23, 31, 67, 72, 20, 142, 131, 44, 77, 113, 65, 86, 105, 56, 15, 119, 109, 99, 82, 16, 112, 35, 136, 43, 76, 121, 73, 45, 98, 106, 26, 141, 84, 127, 70, 143, 92, 118, 27, 117, 101, 130, 66, 30, 140, 81, 9, 114, 47, 54, 19, 91, 110, 17, 79, 80, 139, 34, 58, 3, 71, 24, 85, 48, 107, 120, 50, 33, 90, 51, 108, 96, 129, 60, 12, 102, 40, 133, 115, 28, 2, 116, 138, 57, 4, 69, 32, 83, 103, 55, 53, 49, 0, 97, 122]
[135, 85, 65, 80, 63, 118, 51, 140, 102, 6, 41, 50, 141, 55, 21, 52, 1, 9, 72, 5, 66, 103, 79, 49, 119, 109, 107, 134, 114, 54, 61, 44, 142, 71, 117, 43, 19, 112, 13, 100, 31, 22, 14, 139, 91, 2, 33, 115, 10, 99, 78, 37, 143, 116, 106, 15, 96, 122, 136, 26, 38, 56, 132, 53, 128, 127, 76, 126, 94, 29, 87, 73, 125, 88, 81, 69, 25, 108, 4, 68, 64, 60, 77, 20, 110, 3, 24, 120, 0, 92, 86, 67, 46, 89, 130, 28, 98, 104, 40, 105, 11, 17, 39, 30, 95, 129, 83, 57, 62, 82, 97, 8, 74, 113, 133, 70, 35, 12, 90, 23, 59, 121, 137, 16, 47, 32, 58, 111, 84, 45, 138, 101, 42, 123, 93, 124, 36, 75, 27, 34, 7, 131, 18, 48]
[98, 32, 115, 103, 45, 80, 139, 36, 119, 31, 142, 35, 107, 108, 59, 60, 17, 23, 133, 53, 65, 116, 72, 58, 136, 124, 131, 7, 20, 137, 120, 62, 54, 143, 106, 109, 25, 24, 14, 73, 47, 95, 2, 33, 34, 127, 100, 114, 66, 5, 41, 13, 29, 6, 91, 44, 123, 92, 135, 52, 38, 138, 50, 8, 105, 61, 128, 1, 111, 4, 87, 90, 21, 126, 48, 88, 99, 43, 110, 63, 79, 97, 140, 78, 71, 118, 121, 75, 10, 122, 56, 81, 70, 40, 129, 74, 3, 69, 102, 18, 96, 30, 68, 125, 117, 94, 22, 16, 134, 39, 82, 85, 113, 28, 141, 84, 67, 57, 86, 104, 9, 101, 0, 42, 11, 37, 49, 64, 112, 93, 12, 77, 132, 83, 15, 55, 51, 26, 76, 89, 130, 19, 46, 27]
</pre>
Really generating one million unique random permutations of 144 elements would take an estimated 11 hours on one core of my machine.
=={{header|Tcl}}==
{{trans|D}}
| |||