An Array Exercise
May 8, 2018
Depending on your language, you need some kind of ordered map to solve this problem; we use the avl trees of the Standard Prelude:
(define (rank vec) (let ((dict (make-dict <))) (do ((i 0 (+ i 1))) ((= i (vector-length vec))) (set! dict (dict 'insert (vector-ref vec i) (vector-ref vec i)))) (do ((i 0 (+ i 1))) ((= i (vector-length vec)) vec) (vector-set! vec i (+ 1 (dict 'rank (vector-ref vec i)))))))
The first pass stores each array element in an avl tree dict
. The second pass resets each element of the array to its rank in the avl tree, then returns the array. Here’s the example:
> (rank '#(10 8 15 12 6 20 1)) #(4 3 6 1 2 7 1)
You can run the program at https://ideone.com/tF9m40.
Golf solution:
Forgot the test of the second solution:
(Note we use (vector …) instead of the literal #(…) since now we are mutating this argument!).
Solution in J:
a =: 10 8 15 12 6 20 1
1+ (a /: a) i. a
Here is my take on this, using Julia.
function Nums2Ranks(x::Array{Int64, 1})
n = length(x)
if length(unique(x)) != n; println(“the input array must be comprised of distinct integers!”); return []; end
y = Array{Int64}(n)
z = sort(x)
end
Testing with x = [10,8,15,12,6,20,1], as well as some non-valid input data:
0-element Array{Any,1}
Perl6 solution using some interesting standard list functions: antipairs and kv
Quick and dirty solution in Ruby.
I just realised the function name
order_by_rank
is misleading as the result doesn’t include the elements of the original array.rankify
is a better function name. Ohh well.The old Unix way using Bash.
Delete bracket characters from the string representation of an array.
Output one array element per line by transliterating commas to newlines.
Number all output lines to record in the first column the index of each element.
Sort lines numerically on the array elements recorded now in the second column to list them in their rank order.
Number again all output lines to record in the first column the rank of each element.
Sort lines back in the initial order using the index of each element recorded now in the second column.
Cut out the first column, which now contains the rank of each element in the initial order.
Delete extraneous white spaces in each input line.
Paste rank numbers separated by commas in a string within brackets to restore the original array representation.
Here’s a solution in Python using numpy.
Output:
Here’s a solution in C.
Example:
Clojure/Script.
Try online at http://clojurescript.net/.
sbocq’s Clojure/Script can also be written as:
What ?
Tcl version:
proc rank {vector} {
set sorted [lsort -integer $vector]
lmap v $vector { expr [lsearch $sorted $v] + 1 }
}
% rank {10 8 15 12 6 20 1}
4 3 6 5 2 7 1
The implementation provided at https://ideone.com/tF9m40 seems to have a bug. Here’s an input to test on:
‘#(5242882 8388611 2097156 3145733 9437190 8388614 5242889 7340042 2097163 2097166)
The result should be: 5 8 1 4 10 9 6 7 2 3.
But when the ideone code is run, I get 5 8 2 5 10 9 6 7 3 4 .
You can see it in action at https://ideone.com/9dh6b0.