7
\$\begingroup\$

You are given a table that represents the rankings of S subjects according to a number C of different criteria. The purpose is to

  • compute an overall ranking according to a weighted sum of the C ranking criteria,
  • using one of those criteria (i.e. columns), T, as tie-breaker.

The rankings are a S×C table of positive integers. The weights for computing the overall ranking are given as an array of non-negative numbers.

Entry (s,c) of the table contains the ranking of subject s according to criterion c; that is the position of subject s when all S subjects are sorted according to criterion c. (Another possible interpretation, not used here, would be: row s tells which user is ranked s-th according to criterion c).

Example

Consider the following table with S=6 and C=2:

1   4
4   5
6   1
3   3
5   2
2   6

Weights are

1.5 2.5

and column T=2 is used as tie-breaker.

The overall ranking for the first subject (first row) is 1*1.5+4*2.5 = 11.5. The overall ranking array is

11.5
18.5
11.5
12
12.5
18    

The resulting ranking, which is the output, is then

2
6
1
3
4
5

Note that the first-ranked row is the third, not the first, according to the tie-breaking specification.

Input and output

Use any reasonable format for input and output. The rankings may be a 2D array of any orientation, an array of arrays, or separate arrays. Inputs may be taken in any fixed order.

Input and output rankings should be 1-based (as in the example above), because that's the natural way to speak of rankings.

Output may be a string of numbers with a fixed separator character or an array.

You can write a function or a program.

Test cases

Table, weights, tie-breaking column, output.

--- (Example above) ---

1   4
4   5
6   1
3   3
5   2
2   6

1.5 2.5

2

2
6
1
3
4
5

--- (Three columns) ---

4     4     1
2     3     5
5     1     3
3     5     2
1     2     4

0.5   1.4   0.9

1

3
4
1
5
2

--- (Only one weight is nonzero) ---

1     5
3     3
4     2
5     1
2     4

1     0

2

1
3
4
5
2

--- (Only one column) ---

2
4
1
3

1.25

1

2
4
1
3

--- (Only one row) ---

1 1 1

0.8 1.5 2

3

1    
\$\endgroup\$
2
\$\begingroup\$

Jelly, 11 10 bytes

-1 byte by @Dennis

×⁵S€żị@€ỤỤ

Uses the fact that lists are lexicographically ordered.

This is a dyadic link that takes two arguments plus one input. The left argument is x, the rankings. The right argument is y, the tiebreaker. The input is the weights.

×⁵S€żị@€ỤỤ         Dyadic function. Inputs: x, y
×⁵                 Vectorized multiply x by the weights.

  S                Sum the rows.
                   This is the weighted ordering.
   ż               Zip with
    ị@€             x indexed at y, mapped over x
       ỤỤ          and compute the inverse of the permutation vector that sorts that.
                   A list is sorted by its inverse permutation, so
                   this is the inverse of the inverse; i.e. the original permutation.

Try it here.

\$\endgroup\$
1
\$\begingroup\$

JavaScript (ES6), 114 bytes

(a,w,t)=>a.map(s=>s.reduce((p,v,c)=>p+v*w[c],0)).map((n,i,b)=>b.map((v,j)=>r+=n>v|v==n&a[j][t-1]<a[i][t-1],r=1)|r)

Explanation

Fairly straight-forward. Expects an array of rows as arrays, an array of weights as numbers, and the tie-breaker column as a number. Returns an array.

var solution =

(a,w,t)=>
  a.map(s=>                        // for each row s in the criteria table
    s.reduce((p,v,c)=>p+v*w[c],0)  // create an array of the summed weights for each row
  )
  .map((n,i,b)=>                   // for each number n at i in the summed weights array b
    b.map((v,j)=>                  // compare it to each other summed weight
      r+=n>v                       // increment it's rank if n > v
        |v==n&a[j][t-1]<a[i][t-1], // or in case of tie, check the weights in column t
      r=1                          // initialise the rank to 1
    )|r                            // return the rank
  )
<textarea id="table" rows="5" cols="40">4     4     1
2     3     5
5     1     3
3     5     2
1     2     4</textarea><br />
Weights = <input type="text" id="weights" value="0.5   1.4   0.9" /><br />
Tie-Breaker = <input type="number" id="tie" value="1" /><br />
<button onclick="result.textContent=solution(table.value.split('\n').map(x=>x.split(/\s+/).map(n=>+n)),weights.value.split(/\s+/).map(n=>+n),+tie.value)">Go</button>
<pre id="result"></pre>

\$\endgroup\$
1
\$\begingroup\$

MATL, 21 20 bytes

2#2$XSwiY*4#S)tn:tb(

Takes input as a matrix for the table of rankings, then the tie breaking column as a number, then a column vector of weightings for each column. Attempted explanation:

2#2$XS        % specifies 2 inputs/2 outputs for sortrows, takes 2 implicit inputs, 
              % and sorts the matrix of ranks based on the second column. This means
              % ties are automatically broken in the correct way
wiY*          % swap the top 2 elements in the stack, take an input, and matrix multiply
              % the (sorted) ranking table by the weighting vector to give ranking array
4#S)         % sort the ranking array, taking only the permutation vector, and use it to
              % reorder the original sortrows permutation vector
tn:           % make a vector 1:(number of rows in ranking table)
tb(           % index 1:n vector using permutation vector to give final ranking
% implicit display

Try it Online!

(Written using MATL version 11.0.3 from a few weeks ago)

The equivalent Matlab code may be easier to understand:

[f,g]=sortrows(A,c); % 2#2$XS          (A=matrix of ranks, c=tie-break column)
[~,l]=sort(f*B);     % wiY*4#S        (B=weighting vector)
t=1:numel(g);        % 
t(g(l))=t            % )tn:tb(   
\$\endgroup\$
  • \$\begingroup\$ This should be able to be golfed further.... \$\endgroup\$ – David Feb 15 '16 at 0:42
  • \$\begingroup\$ Nice approach! A recent addition that will save you 1 byte: 4#S instead of FT#S (when the number specified to # exceeds the allowed outputs, it is interpretted as ...FFTFF..) \$\endgroup\$ – Luis Mendo Feb 15 '16 at 13:23
  • \$\begingroup\$ When doing this I was thinking that something like that should be possible. I just read the spec and understand, it's a nice way to do it! \$\endgroup\$ – David Feb 15 '16 at 21:32
1
\$\begingroup\$

MATL, 16 bytes

Y*2GiY)v!4#XS4#S

Input is of the form: weights; table with each ranking on a different row; tie-breaker. Foe example,

[1.5 2.5]
[1 4 6 3 5 2; 4 5 1 3 2 6]
2

Try it online! First test case, second, third, fourth, fifth.

Y*         % implicitly input ranking table and weights. Matrix multiply, to produce
           % combined ranking as a row vector
2G         % push ranking table again
i          % input tie-breaker
Y)         % get that ranking from the table (as a row)
v!         % join combined ranking and tie-breaker column. Produce 2-col matrix
4#XS       % sort rows by first column (combined ranking) and then second
           % column (tie-breaker). Produce not the sorted matrix, but the indices
           % of the sorting, as a column vector
4#S        % sort that vector and get the indices of the sorting. Implicitly display
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.