14
\$\begingroup\$

There is a competition with \$n\$ participants in total. Alice is one of the participants. The outcome of the competition is given as a ranking per participant with a possibility of ties; e.g. there can be three participants who won 2nd place, and the next best participant gets the 5th place.

More rigorously, a participant's rank is defined as the number of other participants who performed strictly better than them plus 1.

If Alice scored \$k\$th place in the competition, what is the number of possible distinct outcomes of the competition? Two outcomes are distinct if there exists a participant whose ranking is different between the two.

As a worked example, let's say \$n = 3\$ and the participants are Alice, Bob, and Charlie. If Alice is 1st, Bob is 2nd, and Charlie is 3rd, the outcome can be written as {Alice: 1, Bob: 2, Charlie: 3}, or [1, 2, 3] in short. This outcome is distinct from [1, 3, 2] or [1, 2, 2]. This notation is used in the test cases below.

Assume that \$n\$ and \$k\$ are integers and \$1 \le k \le n\$.

Standard rules apply. The shortest code in bytes wins.

Test cases

n, k -> ans (possible rankings; Alice is the first in the array)
1, 1 -> 1 ([1])
2, 1 -> 2 ([1,1], [1,2])
2, 2 -> 1 ([2,1])
3, 1 -> 6 ([1,1,1], [1,1,3], [1,3,1], [1,2,2], [1,2,3], [1,3,2])
3, 2 -> 4 ([2,1,3], [2,3,1], [2,2,1], [2,1,2])
3, 3 -> 3 ([3,1,1], [3,1,2], [3,2,1])
4, 1 -> 26
4, 2 -> 18
4, 3 -> 18
4, 4 -> 13

For a given \$n\$, sum of outputs over \$1 \le k \le n\$ is A000670. The output for \$k = 1\$ is A000629.

Imaginary brownie points for answers that solve the challenge without generating all possible rankings.

\$\endgroup\$
5
  • \$\begingroup\$ To be clear, distinct outcomes includes which specific person got which place? \$\endgroup\$
    – xnor
    Feb 7 at 3:05
  • \$\begingroup\$ @xnor Yes, two outcomes are distinct if at least one participant has different ranks. \$\endgroup\$
    – Bubbler
    Feb 7 at 3:13
  • \$\begingroup\$ Somewhat related - Counts Of Orderings Containing At Most K Of The Kth Class \$\endgroup\$ Feb 7 at 14:05
  • 2
    \$\begingroup\$ I'm not sure how to optimize this, but I'm pretty sure the answer is A000670(k-1) * A000629(n-k) * (n-1)C(k-1); and A000629(m) = 2 * A000670(m) unless m=0. \$\endgroup\$
    – Nitrodon
    Feb 7 at 15:36
  • 1
    \$\begingroup\$ It took me several reads through to figure out that we care about who came in what place out of the players. So there are six ways for a competition of three people to end with first second and third place winners, rather than that being counted as a single possibility. The worked test cases didn't really help me since I couldn't understand what they were representing without this critical piece of information. \$\endgroup\$
    – Wheat Wizard
    Feb 9 at 5:51

13 Answers 13

6
\$\begingroup\$

Python 3, 93 84 77 bytes

-9 bytes thanks to @xnor!

Going for the brownie points, but still exponential runtime ;)

f=lambda n,k,d=1:(n<2or~-n*(f(n-1,k,d+1)*(d!=k-1)+f(n-1,k-d)))/(d-(k==1)or 1)

Try it online!

\$\endgroup\$
2
  • 1
    \$\begingroup\$ I noticed that r only ever appeared in comparison to k, so you can eliminate it: Try it online! \$\endgroup\$
    – xnor
    Feb 7 at 20:44
  • \$\begingroup\$ @xnor thanks! I should've looked a bit closer, just from writing the O(n^2) APL answer I knew this could be done with fewer variables \$\endgroup\$
    – ovs
    Feb 7 at 21:58
4
\$\begingroup\$

Python 3, 124 119 117 bytes

-5 bytes thanks to enzo.

lambda n,k:sum(all(r==sum(q<r for q in s)for r in s)for s in product([k-1],*[range(n)]*(n-1)))
from itertools import*

Try it online!

This uses the sum function two times too many, considering the algorithm doesn't involve any addition at all...

Explanation

The algorithm is pretty simple. Let's assume there are \$n = 3\$ contestants and Alice's rank \$k = 1\$. The ranks that follow will be 0-indexed because it's more convenient to work with. First, it generates a list of possible rankings where Alice's rank, or the first rank in the list, is \$0\$. This is done by taking the Cartesian product of the singleton list \$[0]\$ with \$n - 1 = 2\$ copies of \$[0, 3)\$.

[(0, 0, 0), (0, 0, 1), (0, 0, 2),
 (0, 1, 0), (0, 1, 1), (0, 1, 2),
 (0, 2, 0), (0, 2, 1), (0, 2, 2)]

Then, it knocks out invalid rankings by checking if each rank is equal to "the number of other participants who performed strictly better than them", or in other words, the number of ranks lower than the rank in question.

[(0, 0, 0), (0, 0, 2),
 (0, 1, 1), (0, 1, 2),
 (0, 2, 0), (0, 2, 1)]

Finally, it returns the number of rankings remaining, which is \$6\$.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Amazing answer! -5 bytes \$\endgroup\$
    – enzo
    Feb 7 at 12:35
4
\$\begingroup\$

APL(Dyalog Unicode), 58 57 bytes SBCS

{⍵÷⍨⍺(⊣{n×⍵÷1⌈(⌽-⍺∘=)⍳n←≢⍵}¯1↓⊢/⍤⊢+⊢×(≠∨=∘⍳)∘≢)⍣⍵⊢0,⍨⍵⍴1}

Try it on APLgolf!

A dynamic programming adaption of my recursive Python answer. Runs in \$ \mathcal{O}(n^2) \$. A brute force approach would 25 bytes:

{⊃+⌿⍺=1+↑∪(+/∘.<⍨)¨,⍳⍵⍴⍵}

Try it on APLgolf!

\$\endgroup\$
3
\$\begingroup\$

Nekomata + -n, 11 bytes

RJ:ᵐhmj↕ũh=

Attempt This Online!

RJ:ᵐhmj↕ũh=     Take input n, k
R               Range from 1 to n
 J              Split the range into a list of parts
  :ᵐhm          Replace every element in each part with the head of the part
                For example, [[1],[2,3],[4,5]] -> [[1],[2,2],[4,4]]
      j         Join the list of parts into a single list
       ↕        Take a permutation
        ũ       Remove duplicate permutations
         h=     Check if the head of the list is equal to k

-n counts the number of solutions.

\$\endgroup\$
3
\$\begingroup\$

JavaScript (ES6), 63 bytes

A port of ovs' great Python answer. Now including the optimization suggested by xnor.

Expects (n, k).

f=(n,k,d=1)=>(--n?n*=(~d+k&&f(n,k,d+1))+f(n,k-d):1)/(d-!~-k||1)

Try it online!


JavaScript (ES7), 114 bytes

Expects (n)(k).

n=>k=>eval("for(j=t=n**n;j--;)t-=(a=[...Array(n)].map((_,i)=>x=j/n**i%n|0)).some(r=>a.map(v=>q-=v<r,q=r)|q|~x+k)")

Try it online!

Commented

This is a version without eval() for readability.

n =>                 // outer function taking n
k => {               // inner function taking k
  for(               // loop:
    j = t = n ** n;  //   start with j = t = n ** n, where:
                     //     j = iteration counter
                     //     t = success counter
    j--;             //   stop once j = 0 has been processed
  )                  //
    t -=             //   decrement t for each failure
    ( a =            //   let a[] be an array of n entries,
      [...Array(n)]  //   which are turned into 0-indexed rankings
      .map((_, i) => //   for each value at index i in a[]:
        x =          //     save the last value in x
        j / n ** i   //     fill with an integer in [0 .. n-1],
        % n | 0      //     according to j and i
      )              //   end of map()
    ).some(r =>      //   for each ranking r in a[]:
      a.map(v =>     //     for each ranking v in a[]:
        q -= v < r,  //       decrement q if v < r
        q = r        //       starting with q = r
      )              //     end of map()
      | q            //     some() is triggered if q != 0
      | ~x + k       //     or x != k - 1 (i.e. the last ranking
                     //     is not Alice's ranking)
    );               //   end of some() / end of for()
  return t           // return the success counter
}                    //
\$\endgroup\$
2
\$\begingroup\$

05AB1E, 15 bytes

L¤ãʒ<Ðδ›OQ}€нQO

Port of @totallyhuman's Python answer, so make sure to upvote that answer as well!

Try it online or verify all test cases.

Explanation:

L           # Push a list in the range [1, first (implicit) input-integer n]
 ¤          # Push its last item (without popping): n
  ã         # Cartesian product to get all n-sized lists using [1,n]-ranged integers
   ʒ        # Filter it by:
    <       #  Decrease all values in the list by 1
     Ð      #  Triplicate the list
      δ     #  Pop two, and apply double-vectorized:
       ›    #   Larger than check
        O   #  Sum each inner list/row together
         Q  #  Check if this list of sums equals the original list we've triplicated
     }€н    # After the filter: only leave the first item of each remaining list
        Q   # Check for each whether it equals the second (implicit) input-integer k
         O  # Sum those checks together
            # (which is output implicitly as result)
\$\endgroup\$
2
\$\begingroup\$

Jelly, 27 bytes (fast version)

cⱮ`€U;ḋ¥ƒ1H1¦ṖṚ,Ʋ⁹ịⱮPḤ×c×÷⁸

A dyadic Link that accepts \$n\$ on the left and \$k\$ on the right and yields the count of weak orderings given a labelled item's rank.

Try it online! Or see the test-suite.

How?

First calculates the first \$n+1\$ Fubini numbers (A000670): \$F(a) \forall a \in [0,n]\$.

This is achieved by expanding the recursive calculation \$F(a) = \sum_{j=1}^a{F(a-j)\binom{a}{j}}, F(0)=1\$ as a reduction of dot-products over the relevant portion of Pascal's triangle. (I think this can probably be golfed a little by using the recursive calculation itself.)

Then uses that to calculate half of the number of necklaces of partitions of n+1 labelled beads (\$\frac{1}{2}\$A000629) which is simply \$F\$ but with the first term halved: \$\frac{N(a)}{2} \forall a \in [0,n]\$

Finally applies the formula suggested by Nitrodon in the comments:

$$R(n,k)=F(k-1)N(n-k)\binom{n-1}{k-1}$$

cⱮ`€U;ḋ¥ƒ1H1¦ṖṚ,Ʋ⁹ịⱮPḤ×c×÷⁸ - Link: n, k
   €                        - for each {v in [1..n]}:
 Ɱ`                         -   map across {w in [1..v]} with:
c                           -     {v} choose {w}
    U                       - reverse each -> [[1C1], [2C2, 2C1], [3C3, 3C2, 3C1], ...]
        ƒ1                  - starting with 1 reduce by:
       ¥                    -   last two links as a dyad f(current, next):
      ḋ                     -     {current} dot-product {next}
     ;                      -     {current} concatenate {that}
                               -> [F(a) for a in [0..n]] = Fubinis
                Ʋ           - last four links as a monad - f(Fubinis):
          H1¦               -   halve the first term
             Ṗ              -   remove the last term
              Ṛ             -   reverse
               ,            -   pair {Fubinis} -> [Necklaces/2, Fubinis]
                 ⁹ịⱮ        - kth element of each -> [N(n-k)/2, F(k-1)]
                    P       - product
                     Ḥ      - double -> F(k-1)*N(n-k)
                       c    - {n} choose {k}
                      ×     - multiply -> F(k-1) * N(n-k) * nCk
                        ×   - multiply by {k}
                         ÷⁸ - divide by {n} -> F(k-1) * N(n-k) * (n-1)C(k-1)
\$\endgroup\$
2
\$\begingroup\$

Ruby, 212 bytes

... but runs in polynomial time!

def f(n)=n<1?1: n*f(n-1)
$r={}
def r(n, k)=$r[[n,k]]=k**n-(1...k).sum{|i|f(k)/f(i)/f(k-i)*$r[[n,i]]}
def q(x)=x<1?1:(1..x).sum{|i|r(x,i)}
def s(n, k)=(0..(n-k)).sum{|e|f(n-1)/f(k-1)/f(n-k-e)/f(e)*q(k-1)*q(n-k-e)}

The final solution is function s, which takes n and k as arguments.

How does it work?

Divides n - 1 people into three categories: those who were strictly better than Alice, those who were equal, and those strictly worse. We know that exactly k - 1 people ranked better than Alice, we just need to iterate over how many were equal: minimum of 0, maximum n - k.

There are 3 auxiliary functions. Function f is just factorial definition. Function r calculates how many ways to distribute n people into exactly k distinct ranks, and must be memoized else the running time goes exponential. Function q calculates how many ways do distribute x people into any number of ranks (it is just a summation of r).

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

Charcoal, 36 bytes

NθNηILΦEXθ⊖θ⊞O﹪÷ιXθ…⁰⊖θθ⊖η⬤ι⁼λLΦι‹νλ

Try it online! Link is to verbose version of code. Explanation: Based on @totallyhuman's Python answer.

Nθ                                      Input `n` as a number
  Nη                                    Input `k` as a number
         θ                              Input `n`
        X                               Raised to power
           θ                            Input `n`
          ⊖                             Decremented
       E                                Map over implicit range
                ι                       Current value
               ÷                        Vectorised integer divided by
                  θ                     Input `n`
                 X                      Vectorised raised to power
                   …                    Range from
                    ⁰                   Literal integer `0` to
                       θ                Input `n`
                      ⊖                 Decremented
              ﹪                         Vectorised modulo
                       θ                Input `n`
            ⊞O                          Concatenated with
                         η              Input `k`
                        ⊖               Decremented
      Φ                                 Filtered where
                           ι            Current list
                          ⬤             All elements satisfy
                                 ι      Current list
                               Φ        Filtered where
                                  ν     Inner element
                                 ‹      Is less than
                                   λ    Outer element
                              L         Take the length
                            ⁼           Equals
                             λ          Current element
     L                                  Take the length
    I                                   Cast to string
                                        Implicitly print
\$\endgroup\$
1
\$\begingroup\$

Jelly, 13 bytes (golf version)

ṗ`<Ɱ`§‘ƊƑƇḢ€ċ

A dyadic Link that accepts \$n\$ on the left and \$k\$ on the right and yields the count of weak orderings given a labelled item's rank.

Try it online! Or see the test-suite.

How?

ṗ`<Ɱ`§‘ƊƑƇḢ€ċ - Link: n, k
ṗ`            - {n} Cartesian power {n} -> all length n words of alphabet [1..n]
         Ƈ    - filter keep those for which:
        Ƒ     -   is invariant under?:
       Ɗ      -     last three links as a monad - f(word):
  <Ɱ`         -       {word} less than mapped over {word}
     §        -       sums -> [count of elements less than i for i in word]
      ‘       -       increment {those}
                 -> all valid rankings
          Ḣ€  - head each -> Alice's rank in each valid ranking
            ċ - count occurrences of {k}
\$\endgroup\$
0
\$\begingroup\$

Python3, 222 bytes

from itertools import*
R=range
def f(n,k):
 t=0
 q=[(1,{*R(n)},{})]
 for a,b,c in q:
  if not b:t+=c.get(k,[-1])[0]==0
  else:
   for i in R(len(b)):
    for C in combinations(b,i+1):q+=[(a+i+1,b-{*C},{**c,a:C})]
 return t

Try it online!

\$\endgroup\$
0
\$\begingroup\$

JavaScript (Node.js), 120 bytes

n=>g=(k,...s)=>(s[n-1]?k==s[0]&[...s].sort((a,b)=>a-b).every(u=(t,i)=>t==u|(u=t)==i+1):g(k,n,...s))+(--s[0]?g(k,...s):0)

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Desmos, 102 bytes

f(n,k)=∑_{a=0}^{n^n/n-1}0^{[(B[B<i].count-i)^2fori=B].max}
B=mod(floor((na+(k-1)n^n)/n^{[1...n]}),n)

Try It On Desmos!

Try It On Desmos! - Prettified

Eh, this is so scuffed but it works so whatever lmao.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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