An Array Exercise

May 8, 2018

We worked on linked lists in the previous exercise, so today we will work on arrays:

Given an array of distinct integers, replace each element of the array with its corresponding rank in the array. For instance, the input array [10,8,15,12,6,20,1] is replaced by the output array [4,3,6,5,2,7,1] because element 1 has rank 1, element 6 has rank 2, element 8 has rank 3, element 10 has rank 4, element 12 has rank 5, element 15 has rank 6, and element 20 has rank 7.

Your task is to write a program to replace array elements by their rank. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Advertisement

Pages: 1 2

Posted by programmingpraxis
Filed in Exercises
19 Comments »

19 Responses to “An Array Exercise”

  1. James Curtis-Smith said
    May 8, 2018 at 9:34 AM

    Golf solution:

    perl -E 'say"@{[map{$a=$_;1+grep{$_<$a}@ARGV}@ARGV]}";' 10 8 15 12 6 20 1
  2. Pascal Bourguignon said
    May 8, 2018 at 9:48 AM 
    
;; First idea:
;; - wrap the elements with their original position,
;; - sort the wrapping by element,
;; - replace the elements by their rank = position in the sorted vector,
;; - sort the wrapping by the original position,
;; - unwrap.
;; The principle is simple, and we obtain easily a correct solution:

(defun vector-ranks (vector)
  ;; This is O(nlogn+n+nlogn+n) = O(nlogn) in time,
  ;; and O(3n)=O(n) in space.
  ;; Original vector is not modified.
  (map 'vector (function cdr)
       (sort (map 'vector (let ((rank 0))
                            (lambda (entry)
                              (setf (cdr entry) (incf rank))
                              entry))
                  (sort (map 'vector (let ((position -1))
                                       (lambda (element) (cons (incf position) element)))
                             vector)
                        (function <)
                        :key (function cdr)))
             (function <)
             :key (function car))))

(assert (equalp (vector-ranks #(10 8 15 12 6 20 1))
                #(4 3 6 5 2 7 1)))

;; If you insist on mutation:
(defun program-to-replace-vector-elements-by-their-rank (vector)
  (replace vector (vector-ranks vector)))



;; Then, we can see that since we have the position in the sorted
;; wrapping, we can update directly the original vector without
;; re-sorting and unwrapping, thus obtaining an optimized solution:

(defun replace-vector-by-rank (vector)
  ;; This is O(nlogn+n) = O(nlogn) in time,
  ;; and O(n) in space.
  ;; Original vector is modified.
  (let ((sorted (sort (map 'vector (let ((position -1))
                                     (lambda (element) (cons (incf position) element)))
                           vector)
                      (function <)
                      :key (function cdr))))
    (loop
      :for rank :from 1
      :for (position) :across sorted
      :do (setf (aref vector position) rank))
    vector))
  3. Pascal Bourguignon said
    May 8, 2018 at 9:49 AM

    Forgot the test of the second solution:

    (assert (equalp (replace-vector-by-rank (vector 10 8 15 12 6 20 1))
                #(4 3 6 5 2 7 1)))

    (Note we use (vector …) instead of the literal #(…) since now we are mutating this argument!).

  4. Seán Stickle said
    May 8, 2018 at 12:49 PM

    Solution in J:

    a =: 10 8 15 12 6 20 1
    1+ (a /: a) i. a

  5. matthew said
    May 8, 2018 at 1:15 PM 
    >>> a = [10,8,15,12,6,20,1]
>>> n = len(a)
>>> r = sorted(range(n),key=lambda i: a[i])
>>> for i in range(n): a[r[i]] = i+1
>>> a
[4, 3, 6, 5, 2, 7, 1]
  6. Zack said
    May 8, 2018 at 1:26 PM

    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)

    for i = 1:n
    y[i] = find(z .== x[i])[1]
end

return y

    end

    Testing with x = [10,8,15,12,6,20,1], as well as some non-valid input data:

    Nums2Ranks(x)
    7-element Array{Int64,1}:
    4
    3
    6
    5
    2
    7
    1

    Nums2Ranks([1,1,5])
    the input array must be comprised of distinct integers!

    0-element Array{Any,1}

  7. mcmillhj said
    May 8, 2018 at 3:16 PM

    Perl6 solution using some interesting standard list functions: antipairs and kv

    sub rankify(@numbers) {
  @numbers.antipairs().sort(
    { $^a.key <=> $^b.key }
  ).kv().map(
    sub ($rank, $pair) {
      $pair.value => $rank + 1
    }
  ).sort(
    { $^a.key <=> $^b.key }
  ).map({ .value });
}

say rankify([10, 8, 15, 12, 6, 20, 1]);
# (4 3 6 5 2 7 1)
  8. kbob said
    May 8, 2018 at 7:14 PM 
    >>> from itertools import count
>>> a = [10, 8, 15, 12, 6, 20, 1]
>>> s = dict(zip(sorted(a), count(1)))
>>> [s[e] for e in a]
[4, 3, 6, 5, 2, 7, 1]
  9. V said
    May 9, 2018 at 12:36 AM

    Quick and dirty solution in Ruby.

    def order_by_rank(xs)  
  xs.map { |x| 1 + xs.sort.find_index(x) }
end

# Test
order_by_rank([10,8,15,12,6,20,1])

# Outputs
[4, 3, 6, 5, 2, 7, 1]
  10. V said
    May 9, 2018 at 12:50 AM

    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.

  11. sbocq said
    May 10, 2018 at 5:49 PM

    The old Unix way using Bash.

    $ { tr -d '[]'|tr ',' $'\n'|cat -n|sort -n -k2|cat -n|sort -n -k2,2|cut -f1|tr -d ' '|echo "[$(paste -sd "," -)]"; } <<< "[10,8,15,12,6,20,1]"
[4,3,6,5,2,7,1]

    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.

  12. Daniel said
    May 10, 2018 at 8:35 PM

    Here’s a solution in Python using numpy.

    import numpy as np

def replace_with_ranks(array):
    array[np.argsort(array)] = np.arange(1,len(array)+1)

array = np.array([10,8,15,12,6,20,1])
replace_with_ranks(array)
print array

    Output:

    [4 3 6 5 2 7 1]
  13. Daniel said
    May 10, 2018 at 9:19 PM

    Here’s a solution in C.

    #include <stdio.h>
#include <stdlib.h>

typedef struct {
  int value;
  size_t index;
} indexed_int_t;

static int compar(const void* a, const void* b) {
  int a_value = (*(indexed_int_t*)a).value;
  int b_value = (*(indexed_int_t*)b).value;
  if (a_value < b_value) return -1;
  if (a_value > b_value) return 1;
  return 0;
}

void replace_with_ranks(int* array, size_t n) {
  indexed_int_t* indexed_array = malloc(n * sizeof(indexed_int_t));
  for (size_t i = 0; i < n; ++i) {
    indexed_array[i].value = array[i];
    indexed_array[i].index = i;
  }
  qsort(indexed_array, n, sizeof(indexed_int_t), compar);
  for (size_t i = 0; i < n; ++i) {
    array[indexed_array[i].index] = i + 1;
  }
  free(indexed_array);
}

int main(int argc, char* argv[]) {
  size_t n = argc - 1;
  int* array = malloc(n * sizeof(int));
  for (size_t i = 0; i < n; ++i) {
    array[i] = atoi(argv[i+1]);
  }
  replace_with_ranks(array, n);
  printf("[");
  for (size_t i = 0; i < n; ++i) {
    if (i > 0) printf(", ");
    printf("%d", array[i]);
  }
  printf("]\n");
  free(array);
  return EXIT_SUCCESS;
}

    Example:

    $ ./replace_with_ranks 10 8 15 12 6 20 1
[4, 3, 6, 5, 2, 7, 1]
  14. Sam said
    May 12, 2018 at 5:02 AM 
    #lang racket/base

(define (rank-sort xs)
  (sort xs < #:key car #:cache-keys? #t))

(define (ranky v)
  (define ordered
    (rank-sort
     (for/list ([j (in-vector v)]
                [i (in-naturals)])
       (cons j i))))

  (let ([v2 (make-vector (vector-length v))])
    (for ([x (in-list ordered)]
          [i (in-naturals 1)])
      (vector-set! v2 (cdr x) i))
    v2))

(ranky #(10 8 15 12 6 20 1))
;; => '#(4 3 6 5 2 7 1)
  15. sbocq said
    May 14, 2018 at 8:36 PM

    Clojure/Script.

    (defn ranks [v]
  (mapv (comp inc first)
        (sort-by second (map-indexed cons (sort-by second (map-indexed vector v))))))

(ranks [10 8 15 12 6 20 1])
[4 3 6 5 2 7 1]

    Try online at http://clojurescript.net/.

  16. Andrew said
    May 15, 2018 at 10:48 PM

    sbocq’s Clojure/Script can also be written as:

    (defn ranks [v]
  (->> v
       (map-indexed vector)
       (sort-by second)
       (map-indexed cons)
       (sort-by second)
       (mapv (comp inc first))))
  17. WWW.ХХХ.UFZSN.ХУZ said
    May 18, 2018 at 2:58 PM

    What ?

  18. Jef said
    May 18, 2018 at 9:33 PM

    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

  19. B said
    May 21, 2018 at 2:30 AM

    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.

Leave a Reply

Fill in your details below or click an icon to log in:

Gravatar
WordPress.com Logo

You are commenting using your WordPress.com account. ( Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. ( Log Out /  Change )

Cancel

Connecting to %s

%d bloggers like this: