Bigger To The Right
March 9, 2021
The obvious solution is to count at each item in the list, which takes times O(n²):
(define (f1 xs)
(define (gt? x) (lambda (y) (< x y)))
(let loop ((xs xs) (zs (list)))
(if (null? xs) (reverse zs)
(loop (cdr xs) (cons (length (filter (gt? (car xs)) (cdr xs))) zs)))))
An O(n log n solution is available using some sort of balanced binary tree. Working right to left, we insert each item in the tree, then output for each item the current count of items processed less the rank of the current item in the tree:
(let loop ((xs (reverse xs)) (zs (list)) (t (make-avl <)))
(if (null? xs) zs
(let* ((t (t 'insert (car xs) (car xs)))
(z (- (length zs) (t 'rank (car xs)))))
(loop (cdr xs) (cons z zs) t)))))
Both solutions output the desired (4 3 3 2 2 0 0).
There is no O(n) solution, for exactly the same reason that the best comparison-base sorting algorithms take time O(n log n). And I can’t think of any way to adapt radix sorting to this problem.
You can see all of the code assembled at https://ideone.com/CoCl4p, though it doesn’t run. The Chicken Scheme interpreter at ideone is very old, and sometimes doesn’t work. I assure you the code works on Chez Scheme on my system.
Programming Praxis 
use feature qw(say); say join q( ), max_other( qw(10 12 8 17 0 3 24 19) ); sub max_other { map { $a = shift @_; scalar grep { $_>$a } @_ } @_; }The counts are the number of elements to skip over when doing a (descending) insertion sort from the right. The tree solution is nice – basically this is “tree sort”: https://en.wikipedia.org/wiki/Tree_sort
A solution in Racket:
(define (big-right in) (reverse (cadr (foldl (λ (val init) (list (cdar init) (cons (length (filter (λ (x) (> x val)) (car init))) (cadr init)))) (list in null) in))))Examples:
import java.util.concurrent.atomic.*;
AtomicInteger index = new AtomicInteger();
Arrays.stream(array)
.map(x -> (int)Arrays.stream(array)
.skip(index.incrementAndGet())
.filter(y -> y > x)
.count())
.toArray();
code in c++
#include
using namespace std;
int main()
{
int sum = 0;
int a[6] = { 10, 12, 4, 17, 29, 8 };
int b[6];
for (int i = 0; i < 6; i++)
{
sum = 0;
for (int j = 0; j < 6; j++)
{
if (a[j] > a[i])
sum = sum + 1;
}
b[i] = sum;
}
for (int i = 0; i < 6; i++)
{
cout << b[i] << endl;
}
}
Interesting exercise! I applied iteration on the result, using it as input to compute its “Bigger to the Right”. Interestingly, it is possible to find lists of length n that leads to n lists before getting to [0, 0, …, 0]. Here is an example with a list of 10 elements:
[19, 32, 15, 44, 31, 42, 20, 48, 23, 39]
[8, 4, 7, 1, 3, 1, 3, 0, 1, 0]
[0, 1, 0, 2, 0, 1, 0, 1, 0, 0]
[4, 1, 3, 0, 2, 0, 1, 0, 0, 0]
[0, 2, 0, 2, 0, 1, 0, 0, 0, 0]
[3, 0, 2, 0, 1, 0, 0, 0, 0, 0]
[0, 2, 0, 1, 0, 0, 0, 0, 0, 0]
[2, 0, 1, 0, 0, 0, 0, 0, 0, 0]
[0, 1, 0, 0, 0, 0, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
I have not been able to find the pattern of the initial list to get 10 iterations. Any idea?
a couple of solutions in Racket.
;;; This solution was written in Common Lisp.
(defun calculate-bigger-to-the-right (a)
(map ‘list (lambda (y)
(let ((counter 0) (a y))
(map nil (lambda (x)
(when (> x (car y)) (incf counter))) a) counter))
(mapcon ‘list a)))
A solution in C++:
#include <iterator> #include <numeric> #include <vector> std::vector<int> bigger_to_the_right(const std::vector<int>& vec) { std::vector<int> retval; for (auto iter = vec.begin(); iter != vec.end(); iter = std::next(iter)) { retval.push_back(std::accumulate(std::next(iter), vec.end(), 0u, [&iter](size_t a, int b){ return a + (b > *iter); })); } return retval; }