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
Improve this question
\$\endgroup\$

4 Answers 4

Reset to default
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.

Improve this answer
\$\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>

Improve this answer
\$\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(
Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ This should be able to be golfed further.... \$\endgroup\$ Commented Feb 15, 2016 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\$ Commented Feb 15, 2016 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\$ Commented Feb 15, 2016 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
Improve this answer
\$\endgroup\$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.