Permutations/Rank of a permutation: Difference between revisions

Content added Content deleted
m (→‎{{header|Ruby}}: removed a default argument)
Line 887: Line 887:
include Enumerable
include Enumerable
attr_reader :num_elements, :size
attr_reader :num_elements, :size

def initialize(num_elements)
def initialize(num_elements)
@num_elements = num_elements
@num_elements = num_elements
@pi = (0..num_elements-1).to_a
@size = fact(num_elements)
@size = fact(num_elements)
end
end

def each
def each
return self.to_enum unless block_given?
return self.to_enum unless block_given?
(0..@size-1).each{|i| yield unrank(i)}
(0...@size).each{|i| yield unrank(i)}
end
end

def unrank(r) # nonrecursive version of Myrvold Ruskey unrank2 algorithm.
def unrank(r) # nonrecursive version of Myrvold Ruskey unrank2 algorithm.
pi = @pi.dup
pi = (0...num_elements).to_a
(@num_elements-1).downto(1) do |n|
(@num_elements-1).downto(1) do |n|
s, r = r.divmod(fact(n))
s, r = r.divmod(fact(n))
Line 907: Line 906:
pi
pi
end
end

def rank( pi) # nonrecursive version of Myrvold Ruskey rank2 algorithm.
def rank(pi) # nonrecursive version of Myrvold Ruskey rank2 algorithm.
pi = pi.dup
pi = pi.dup
pi1 = pi.zip(0...pi.size).sort.map(&:last)
pi1 = pi.zip(0...pi.size).sort.map(&:last)
(pi.size-1).downto(0).inject(0) do |memo,i|
(pi.size-1).downto(0).inject(0) do |memo,i|
s = pi[i]
pi[i], pi[pi1[i]] = pi[pi1[i]], (s = pi[i])
pi[i], pi[pi1[i]] = pi[pi1[i]], pi[i]
pi1[s], pi1[i] = pi1[i], pi1[s]
pi1[s], pi1[i] = pi1[i], pi1[s]
memo += s * fact(i)
memo += s * fact(i)
end
end
end
end

private
private
def fact(n)
def fact(n)
return 1 if n.zero?
n.zero? ? 1 : n.downto(1).inject(:*)
n.downto(1).inject(:*)
end
end
⚫
end</lang>

end
⚫
</lang>
Demo:
Demo:
<lang ruby>puts "All permutations of 3 items from and back to rank."
<lang ruby>puts "All permutations of 3 items from and back to rank."
perm = Permutation.new(3)
perm = Permutation.new(3)
(0..perm.size-1).each{|num| puts "#{num} --> #{prm=perm.unrank(num)} --> #{perm.rank(prm)}"}
(0...perm.size).each{|num| puts "#{num} --> #{prm=perm.unrank(num)} --> #{perm.rank(prm)}"}

puts "\n4 random samples of 12 items:"
puts "\n4 random samples of 12 items from and back to rank."
perm = Permutation.new(12)
perm = Permutation.new(12)
4.times{ p perm.unrank(rand(perm.size))}
4.times{ puts "%9d --> %s --> %9d" % [r=rand(perm.size), prm=perm.unrank(r), perm.rank(prm)]}


puts "\n4 random uniq samples of 144 items:"
puts "\n4 random uniq samples of 144 items:"
perm, rands = Permutation.new(144), {}
perm, rands = Permutation.new(144), {}
# generate 1_000_000 unique random numbers in the range (0..144!) (takes about 2.5 seconds)
# 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
rands[rand(perm.size)] = true until rands.size == 1_000_000

random_perms = rands.keys.each.lazy{|k| perm.unrank(k)}
random_perms = rands.each_key.lazy{|k| perm.unrank(k)}
# random_perms is lazy. Generate permutations one by one:
# random_perms is lazy. Generate permutations one by one:
4.times do
4.times{p perm.unrank(random_perms.next)}
p r = random_perms.next
⚫
</lang>
p prm = perm.unrank(r)
p perm.rank(prm) == r
⚫
end</lang>
{{out}}
{{out}}
<pre style="overflow:auto">
<pre style="overflow:auto">
Line 954: Line 953:
5 --> [0, 1, 2] --> 5
5 --> [0, 1, 2] --> 5


4 random samples of 12 items:
4 random samples of 12 items from and back to rank.
[9, 6, 3, 11, 8, 7, 10, 0, 1, 4, 2, 5]
99442243 --> [7, 6, 8, 3, 10, 1, 9, 11, 0, 4, 5, 2] --> 99442243
[5, 1, 0, 9, 6, 4, 3, 2, 7, 11, 10, 8]
337326172 --> [7, 6, 10, 0, 2, 3, 11, 1, 5, 9, 4, 8] --> 337326172
[3, 9, 5, 7, 10, 1, 11, 6, 8, 2, 4, 0]
4778098 --> [9, 6, 7, 5, 2, 8, 11, 4, 10, 3, 1, 0] --> 4778098
[0, 7, 3, 4, 6, 9, 5, 2, 11, 1, 10, 8]
468353447 --> [9, 4, 2, 3, 6, 10, 1, 7, 5, 0, 8, 11] --> 468353447


4 random uniq samples of 144 items:
4 random uniq samples of 144 items:
2764575360456493218947191346199563786344679440083424317164174964729286291440941279012888793089017925404664271586714233946361449878956286173028220761623980334868793458099951877456608056440904453668056576598920423670911869425117449937938198123808117853
⚫
[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]
[98, 65, 31, 138, 68, 69, 10, 35, 143, 17, 49, 90, 100, 58, 79, 37, 89, 94, 11, 122, 5, 119, 47, 123, 128, 41, 67, 75, 33, 13, 8, 55, 80, 99, 85, 81, 45, 126, 115, 59, 133, 44, 140, 113, 54, 142, 125, 127, 50, 20, 70, 36, 60, 72, 52, 86, 134, 18, 96, 61, 114, 56, 1, 112, 109, 26, 2, 62, 97, 88, 57, 16, 83, 22, 76, 64, 129, 117, 121, 136, 73, 34, 27, 48, 3, 137, 104, 132, 101, 32, 7, 23, 25, 30, 4, 78, 6, 120, 28, 19, 42, 111, 124, 43, 135, 118, 131, 14, 40, 29, 51, 92, 93, 77, 95, 116, 106, 139, 91, 66, 102, 63, 84, 130, 21, 12, 38, 105, 141, 74, 46, 0, 39, 24, 108, 53, 15, 87, 107, 9, 82, 110, 103, 71]
true
⚫
[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]
581378746619134421610590787114075883604639790081640446988853702372476235480735354011614748882838959943069972039765230962978435387565720009660107060797009355093335736922722607963964082214822692777188121231234716922053393200924081454086807468556348101
[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]
[19, 48, 16, 89, 72, 109, 46, 34, 3, 52, 66, 122, 56, 119, 47, 84, 67, 88, 135, 113, 142, 4, 103, 124, 75, 31, 86, 81, 143, 2, 96, 117, 127, 39, 41, 33, 71, 106, 54, 17, 140, 83, 80, 68, 77, 125, 28, 38, 1, 139, 53, 35, 78, 65, 22, 10, 123, 20, 116, 23, 62, 32, 108, 29, 120, 128, 59, 111, 82, 64, 43, 42, 141, 70, 85, 57, 91, 44, 7, 61, 137, 45, 130, 132, 100, 112, 26, 58, 50, 55, 131, 27, 0, 74, 114, 115, 104, 95, 76, 73, 79, 5, 51, 93, 101, 24, 94, 8, 110, 138, 133, 92, 69, 134, 25, 87, 118, 121, 60, 126, 40, 36, 18, 98, 9, 99, 12, 129, 30, 107, 90, 63, 21, 97, 14, 49, 37, 13, 102, 105, 6, 136, 11, 15]
true
3862828872557168655028927772314213364838836589595169123363755483846504171095746597867391615687467779932466719611353020149271086793608853169788146783569713115890942229488492262312988677553070567823077055419333248270326769623765923370471995234511383513
⚫
[11, 29, 50, 68, 131, 139, 39, 84, 16, 143, 125, 62, 56, 120, 42, 80, 38, 83, 81, 49, 47, 116, 57, 34, 23, 124, 40, 137, 117, 135, 127, 43, 119, 18, 72, 33, 69, 141, 104, 102, 74, 133, 21, 0, 132, 78, 51, 98, 3, 7, 15, 26, 9, 122, 115, 103, 140, 85, 61, 130, 96, 87, 123, 5, 92, 22, 24, 93, 4, 88, 107, 121, 41, 136, 118, 65, 6, 77, 109, 60, 36, 105, 2, 30, 94, 10, 82, 110, 89, 106, 113, 32, 17, 111, 126, 71, 129, 46, 53, 20, 108, 55, 12, 28, 142, 37, 44, 45, 63, 73, 70, 134, 75, 99, 97, 14, 64, 90, 114, 8, 101, 66, 48, 27, 76, 13, 128, 112, 91, 95, 52, 25, 59, 35, 67, 86, 19, 58, 79, 138, 1, 54, 31, 100]
true
2918302898022044898081980708265879018867198180047026696353345520178885195108521785334274488901945168232326479535713828754624213355248635860483646511664861481065235873861496511507890774391370483865270125811094164531568140755985423978860285012352192610
⚫
[66, 140, 109, 101, 20, 62, 13, 60, 0, 116, 107, 1, 87, 99, 110, 38, 64, 25, 130, 2, 17, 84, 123, 36, 31, 94, 134, 51, 55, 103, 81, 30, 106, 15, 61, 21, 59, 142, 71, 92, 54, 79, 48, 132, 111, 7, 67, 65, 82, 49, 115, 10, 105, 19, 32, 22, 141, 9, 68, 53, 3, 63, 74, 56, 42, 23, 136, 129, 57, 126, 77, 39, 137, 50, 121, 117, 93, 5, 46, 45, 89, 96, 41, 122, 72, 47, 37, 11, 58, 91, 70, 128, 43, 127, 76, 95, 138, 100, 90, 8, 119, 120, 143, 14, 6, 33, 83, 28, 44, 27, 135, 88, 35, 78, 86, 18, 69, 73, 85, 112, 29, 80, 4, 104, 52, 108, 12, 114, 133, 118, 97, 26, 34, 24, 113, 40, 98, 124, 139, 125, 131, 16, 102, 75]
true
</pre>
</pre>
Really generating one million unique random permutations of 144 elements would take an estimated 11 hours on one core of my machine.
Really generating one million unique random permutations of 144 elements would take an estimated 11 hours on one core of my machine.
Retrieved from "https://rosettacode.org/wiki/Permutations/Rank_of_a_permutation"