Rosetta Code

Permutations/Rank of a permutation: Difference between revisions

Page Discussion

Permutations/Rank of a permutation (view source)

Revision as of 09:04, 27 August 2014

1,246 bytes added ,  9 years ago
→‎{{header|Ruby}}
m (→‎{{header|Ruby}}: removed a default argument)
Line 887:
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
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(0.dup..num_elements).to_a
(@num_elements-1).downto(1) do |n|
s, r = r.divmod(fact(n))
Line 907 ⟶ 906:
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|
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]
memo += s * fact(i)
end
end
 
private
def fact(n)
returnn.zero? ? 1 if: n.zero?downto(1).inject(:*)
n.downto(1).inject(:*)
end
end</lang>▼
 
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: from and back to rank."
perm = Permutation.new(12)
4.times{ pputs perm.unrank("%9d --> %s --> %9d" % [r=rand(perm.size), prm=perm.unrank(r), perm.rank(prm)]}
 
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.eacheach_key.lazy{|k| perm.unrank(k)}
# random_perms is lazy. Generate permutations one by one:
4.times do
4.times{ p perm.unrank(r = random_perms.next)}
</lang>▼
p prm = perm.unrank(r)
p perm.rank(prm) == r
▲end</lang>
{{out}}
<pre style="overflow:auto">
Line 954 ⟶ 953:
5 --> [0, 1, 2] --> 5
 
4 random samples of 12 items: from and back to rank.
99442243 --> [97, 6, 8, 3, 1110, 81, 79, 1011, 0, 1, 4, 25, 52] --> 99442243
337326172 --> [57, 16, 010, 90, 62, 43, 311, 21, 75, 119, 104, 8] --> 337326172
[3, 4778098 --> [9, 56, 7, 105, 12, 8, 11, 64, 810, 23, 41, 0] --> 4778098
468353447 --> [09, 74, 32, 43, 6, 910, 51, 27, 115, 10, 108, 811] --> 468353447
 
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]▼
[598, 6365, 1031, 18138, 12568, 3969, 3610, 10035, 8143, 4117, 3749, 790, 78100, 8858, 11179, 637, 89, 1394, 2511, 137122, 1265, 95119, 5947, 11123, 128, 12341, 4667, 9475, 12433, 113, 1358, 3855, 2980, 6299, 6885, 6181, 5245, 21126, 134115, 7559, 93133, 4244, 132140, 104113, 8754, 22142, 64125, 14127, 7450, 2320, 3170, 6736, 7260, 2072, 14252, 13186, 44134, 7718, 11396, 6561, 86, 105114, 56, 151, 119112, 109, 9926, 822, 1662, 11297, 3588, 13657, 4316, 7683, 12122, 7376, 4564, 98129, 106117, 26121, 141136, 8473, 12734, 7027, 14348, 923, 118137, 27104, 117132, 101, 13032, 667, 3023, 14025, 8130, 94, 11478, 476, 54120, 28, 19, 9142, 110111, 17124, 7943, 80135, 139118, 34131, 5814, 340, 7129, 2451, 8592, 4893, 10777, 12095, 50116, 33106, 90139, 5191, 10866, 96102, 12963, 6084, 12130, 10221, 4012, 13338, 115105, 28141, 274, 11646, 1380, 5739, 424, 69108, 3253, 8315, 10387, 55107, 539, 4982, 0110, 97103, 12271]
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
[9819, 3248, 11516, 10389, 4572, 80109, 13946, 3634, 1193, 3152, 14266, 35122, 10756, 108119, 5947, 6084, 1767, 2388, 133135, 53113, 65142, 1164, 72103, 58124, 13675, 12431, 13186, 781, 20143, 1372, 12096, 62117, 54127, 14339, 10641, 10933, 2571, 24106, 1454, 7317, 47140, 9583, 280, 3368, 3477, 127125, 10028, 11438, 661, 5139, 4153, 1335, 2978, 665, 9122, 4410, 123, 9220, 135116, 5223, 3862, 13832, 50108, 829, 105, 61120, 128, 159, 111, 482, 8764, 9043, 2142, 126141, 4870, 8885, 9957, 4391, 11044, 637, 7961, 97137, 14045, 78130, 71132, 118100, 121112, 7526, 1058, 12250, 5655, 81131, 7027, 400, 12974, 74114, 3115, 69104, 10295, 1876, 9673, 3079, 685, 12551, 11793, 94101, 2224, 1694, 1348, 39110, 82138, 85133, 11392, 2869, 141134, 8425, 6787, 57118, 86121, 10460, 9126, 10140, 036, 4218, 1198, 379, 4999, 6412, 112129, 9330, 12107, 7790, 13263, 8321, 1597, 5514, 5149, 2637, 7613, 89102, 130105, 196, 46136, 2711, 15]
true
3862828872557168655028927772314213364838836589595169123363755483846504171095746597867391615687467779932466719611353020149271086793608853169788146783569713115890942229488492262312988677553070567823077055419333248270326769623765923370471995234511383513
▲[13511, 8529, 6550, 8068, 63131, 118139, 5139, 14084, 10216, 6143, 41125, 5062, 14156, 55120, 2142, 5280, 138, 983, 7281, 549, 6647, 103116, 7957, 4934, 11923, 109124, 10740, 134137, 114117, 54135, 61127, 4443, 142119, 7118, 11772, 4333, 1969, 112141, 13104, 100102, 3174, 22133, 1421, 1390, 91132, 278, 3351, 11598, 103, 997, 7815, 3726, 1439, 116122, 106115, 15103, 96140, 12285, 13661, 26130, 3896, 5687, 132123, 535, 12892, 12722, 7624, 12693, 944, 2988, 87107, 73121, 12541, 88136, 81118, 6965, 256, 10877, 4109, 6860, 6436, 60105, 772, 2030, 11094, 310, 2482, 120110, 089, 92106, 86113, 6732, 4617, 89111, 130126, 2871, 98129, 10446, 4053, 10520, 11108, 1755, 3912, 3028, 95142, 12937, 8344, 5745, 6263, 8273, 9770, 8134, 7475, 11399, 13397, 7014, 3564, 1290, 90114, 238, 59101, 12166, 13748, 1627, 4776, 3213, 58128, 111112, 8491, 4595, 13852, 10125, 4259, 12335, 9367, 12486, 3619, 7558, 2779, 34138, 71, 13154, 1831, 48100]
true
2918302898022044898081980708265879018867198180047026696353345520178885195108521785334274488901945168232326479535713828754624213355248635860483646511664861481065235873861496511507890774391370483865270125811094164531568140755985423978860285012352192610
▲[1266, 130140, 62109, 35101, 6020, 9562, 213, 3160, 540, 61116, 51107, 181, 4887, 11899, 32110, 12438, 1764, 925, 122130, 102, 8617, 13784, 24123, 9036, 5731, 13894, 120134, 9451, 5355, 3103, 4081, 1530, 69106, 1115, 2261, 13421, 8759, 143142, 11571, 892, 12954, 4979, 4348, 50132, 97111, 167, 4167, 12765, 9382, 11949, 73115, 610, 65105, 10619, 5532, 10022, 88141, 429, 6468, 553, 1213, 7763, 13174, 7256, 12642, 11323, 78136, 0129, 4657, 68126, 3977, 7639, 116137, 3450, 107121, 110117, 13993, 265, 8346, 3845, 14189, 8096, 5641, 84122, 2372, 14247, 11137, 7511, 8258, 10391, 70, 21128, 12343, 66127, 10476, 9695, 27138, 135100, 3390, 18, 140119, 37120, 81143, 10514, 1126, 13233, 10283, 9228, 1444, 13627, 91135, 2088, 735, 1378, 2586, 5918, 3669, 13373, 7985, 19112, 6329, 4580, 284, 67104, 10952, 85108, 10812, 114, 44133, 128118, 9997, 10126, 434, 8924, 117113, 4740, 2998, 52124, 98139, 74125, 30131, 12516, 58102, 7175]
true
</pre>
Really generating one million unique random permutations of 144 elements would take an estimated 11 hours on one core of my machine.
Anonymous user
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/220679"