Как оптимизировать данный код?

Question

[codymaverick]

Есть такой код на JS. Это решение задачи на CodeWars. Все тесты она проходит, но у сервера есть ограничение по времени. Нужно как то оптимизировать данный код, или отдельные его части. Как можно это сделать?

Код

function chooseBestSum(t, k, ls) {
    if (ls.length <= 1) {
        return null;
    } else {
        function PermutationsWithRepetition(ls, k) {
            var K = k - 1, z = 0,
                N = ls.length, n = 0,
                out = [],
                stack = [];
            function next() {
                while (true) {
                    while (n < ls.length) {
                        out[z] = ls[n++];
                        if (z == K) return out.slice(0);
                        else {
                            if (n < ls.length) {
                                stack.push(z);
                                stack.push(n);
                            }
                            z++;
                            n = 0;
                        }
                    }
                    if (stack.length == 0) break;
                    n = stack.pop();
                    z = stack.pop();
                }
                return false;
            }
            function each(cb) {
                var v;
                while (v = next()) if (cb(v) === false) return;
            }
            return {
                each: each
            };
        }               
        let perms = PermutationsWithRepetition(ls, k),
            summArray = [],
            closest;
        perms.each(function (v) {
            function isCopy() {
                for (let j = 0; j <= v.length; j++) {
                    for (let i = 0; i <= v.length; i++) {
                        if (j !== i) {
                            if (v[j] === v[i])
                                return true;
                        }
                    }
                }
            }
            if (isCopy(v) === undefined) {
                summArray.push(v.reduce((sum, current) => sum + current));
            }
        })
        summArray.forEach(item => {
            if (item <= t && (typeof closest === 'undefined' || closest <= item)) {
                closest = item;
            }
        })
        return closest ? closest : null;
    }
}

Comments

[codymaverick]

MaxKorz, если вызвать функцию в консоле и передать ей аргументы, то функция возвращает число

Answer 1

[Сергей Соколов]

В код вникать не хочется, но оптимизировать можно вот, что:

1. не перебирать все возможные комбинации. Если отсортировать входной массив по возрастанию, можно остановиться на трёх подряд элементах, превышающих суммой лимит. Если в переборе пробуете менять наибольший элемент, а сумма уже превышена, искать правее уже не нужно.
   
2. отбросить сразу крайние случаи вроде t == 0 или t < наименьшего из элементов - подумайте, какие ещё;
   

Upd. я такое решение сделал, прошло. Не оптимизировал, полный перебор идёт.

spoiler

function chooseBestSum(t, k, ls) {

  /**
   * make next combination of N on bits in a 32-bit integer
   */
  function nextPerm(x) {
    // via https://stackoverflow.com/questions/506807/creating-multiple-numbers-with-certain-number-of-bits-set
    if (x === 0) return 0;
    const smallest     = (x & -x);
    const ripple       = x + smallest;
    const new_smallest = (ripple & -ripple);
    const ones         = ((new_smallest/smallest) >> 1) - 1;
    return ripple | ones;
  }

  let bestSum = null, bestN;
  const len = ls.length;
  if (len > 31) throw "Too many (over 31) options for this algorithm";
  const maxmask = (1 << len) - 1;
  
  if (len < k) return null; // not enough distances
  
  ls.sort((a, b) => a - b); // todo: skip checking rest of combinations once solid selection of elements exceeds t

  let mask = (1 << k) - 1; // initial mask value with k less significant bits on
  
  let sum, pos, n;
  while(true) {
    for(sum = 0, n = 0, pos = 0; pos < 32; pos++) {
      if (mask & (1 << pos)) {
        sum += ls[pos];
        if (++n === k) break;
      }
    }

    if (sum > bestSum && sum <= t) {
      bestSum = sum;
      bestN = mask;
    }
    
    mask = nextPerm(mask);
    
    if (mask > maxmask) break;
    if (mask < 0) break;
  }
  
  return bestSum;
}