Ищу помощь в объяснении для большого алгоритма комбинации - PullRequest
Новая
       5

Ищу помощь в объяснении для большого алгоритма комбинации

1 голос
/ 16 января 2020

Недавний CodeSignal Challenge должен был вычислить 1000C500 (мод 1e9 + 7), и я потерпел поражение.

Все мои испытания превысили ограничение по времени. Вот лучшее решение 1012 * от psr . Кто-нибудь может объяснить, что происходит в этой строке? Я изучил ES6, но понятия не имел о его синтаксисе f[o = n + 1/k] = o in f ... 

f = nCk = (n, k) => f[o = n + 1/k] = o in f
    ? ...
    : ... 
        ? n && ...
        : ...

Некоторые строки маскируются, чтобы избежать нарушения правила

1 Ответ

0 голосов
/ 17 января 2020

Благодаря объяснению Барбара в комментарии к вопросу, теперь я понимаю алгоритм.

Алгоритм можно переписать следующим образом: 

f = nCk = (n, k) => {   //Declare both f and nCk as the same function
let o = n + 1/k         //o will be the key of function object f
f[o] = o in f           //Define f[o] based on a nested ternary expression
    ? f[o]              //Avoid recalculation if f has key o already 
    : k==0              //nC0 is always 1
        ? 1
        : n<k           //nCk is improper and assigned 0 if n<k
            ? 0
            : f(--n, k) //Do recursion nCk = (n-1)Ck + (n-1)C(k-1)
            + f(n, k - 1) 
return f[o]             //Done!
}

Вот пример 5C2 

f(n,k)  n   k   o   f[o]
f(5,2)  5   2   5.5 f[5.5]=f(4,2)+f(4,1)=10
f(4,2)  4   2   4.5 f[4.5]=f(3,2)+f(3,1)=6
f(3,2)  3   2   3.5 f[3.5]=f(2,2)+f(2,1)=3
f(2,2)  2   2   2.5 f[2.5]=f(1,2)+f(1,1)=1
f(1,2)  1   2   1.5 f[1.5]=f(0,2)+f(0,1)=0
f(0,2)  0   2   0.5 f[0.5]=0
f(0,1)  0   1   1   f[1]=0
f(1,1)  1   1   2   f[2]=f(0,1)+f(0,0)=1
f(0,0)  0   0   Inf f[Inf]=1 //Inf aka Infinity
f(2,1)  2   1   3   f[3]=f(1,1)+f(1,0)=2
f(1,0)  1   0   Inf f[Inf]=1
f(3,1)  3   1   4   f[4]=f(2,1)+f(2,0)=3
f(n,0)  n   0   Inf f[Inf]=1
f(4,1)  4   1   5   f[5]=f(3,1)+f(3,0)=4

PS Я получил несколько выводов при изучении этого алгоритма

  1. Двойное объявление функции в той же строке, что и трюк для рекурсии

  2. Немедленное использование ключа с только что присвоенным значением

  3. Бесконечность может использоваться как ключ объекта (!)

  4. Синтаксис o in f проверяет, имеет ли объект f ключ o

...