Сгенерируйте все возможные уникальные комбинации положительных чисел, сумма которых равна N

Это моя функция — генерировать все возможные уникальные комбинации положительных чисел, сумма которых равна N.

Например:

• Если вход 4

• Результат должен быть: [ '4', '1+3', '1+1+2', '1+1+1+1', '2+2' ]

Вы можете попробовать онлайн здесь

const f=n=>{ // n is a positive number
  if(n==0) return ["0"]
  if(n==1) return ["1"]
  if(n==2) return ["0+2", "1+1"]
  const result = [n+"+0"]
  for(let i=n-1; i>=n/2|0; i--){
    for(const x of (f(n-i) || [])) {
      for(const y of (f(i) || [])) {
        result.push(y + "+" + x)
      }
    }
  }

  // Remove duplicated records
  const map = result.map(v=>v.split`+`.filter(x=>+x>0).sort((m,n)=>m-n).join`+`)
  return [...new Set(map)]
}

//Testing
a=f(8)
console.log(a)

Мой подход использует рекурсию, он работает так:

• Если я смогу найти все возможные уникальные комбинации положительных чисел, их сумма будет равна N.

• Затем я могу найти все возможные уникальные комбинации положительных чисел, сумма которых равна N + 1.

Например:

• Если все возможные уникальные комбинации положительных чисел имеют сумму, равную 3, следующие: ["3", "1+2", "1+1+1"] и все возможные уникальные комбинации положительных чисел, сумма которых равна 2, равны ["2", "1+1"]

• Тогда для 4 так должно быть:

1. 4 + 0 или же 4

2. Все возможные уникальные комбинации комбинаций положительных чисел имеют сумму, равную 3 а также 1

// for 3 it's combinations is
["3", "1+2", "1+1+1"]
// for 1 it is
["1"]

3. Все возможные уникальные комбинации комбинаций положительных чисел имеют сумму, равную 2 а также 2,

// for 2 it's combinations is
["2", "1+1"]

И я делаю циклы только до целого числа n/2 чтобы избежать дублирования.

Не могли бы вы помочь мне его просмотреть?

const f=n=>{ // n is a positive number
  if(n==0) return ["0"]
  if(n==1) return ["1"]
  if(n==2) return ["0+2", "1+1"]
  const result = [n+"+0"]
  for(let i=n-1; i>=n/2|0; i--){
for(const x of (f(n-i) || [])) {
  for(const y of (f(i) || [])) {
    result.push(y + "+" + x)
  }
}
  }

  // Remove duplicated records
  const map = result.map(v=>v.split`+`.filter(x=>+x>0).sort((m,n)=>m-n).join`+`)
  return [...new Set(map)]
}

//Testing
a=f(8)
console.log(a)

Рассмотрение

Ваш код — хорошее простое решение. Стиль неряшливый. Сложность немного высока, и используемые методы негативно влияют на производительность.

Буквальный вызов шаблона Array.split`+` меня всегда подбрасывает, но мне это нравится, ваш код напоминает мне использовать его почаще.

Общие моменты

• Разделите все блоки кода. Например if(n==0) return ["0"] лучше как if(n==0) { return ["0"] }

  Почему? JavaScript, как и большинство языков стиля C, не требует блоков с разделителями для блоков с одним оператором, однако при изменении кода очень легко просмотреть недостающие блоки. {}.

• Используйте точку с запятой или хорошо изучите автоматическая вставка точки с запятой (ASI)

• Вместо того, чтобы использовать continue рассмотрите возможность использования заявления } else {

  Почему? continue ломает использование отступов, которые визуально помогают вам увидеть поток с первого взгляда. continue и его друг break по возможности следует избегать.

// Avoid using continue to skip code

for (a of list) {
    if (foo) { 
        ...do something...
        continue;
    }
    ...lots of code...
}

// Rather use an else statement

for (a of list) {
    if (foo) { 
        ...do something...
    } else {
        ...lots of code...
    }
}

• Пробелы между операторами i>=n/2|0 должно быть i >= n / 2 | 0

• При использовании выражений короткого замыкания (f(n) || []) использовать Нулевой оператор объединения ?? например f(n) ?? [] вместо логического ИЛИ ||

• В двух внутренних циклах вы выполняете рекурсию с вызовом (f(n) || []). Функция f() всегда возвращает массив, поэтому нет необходимости в || []

• В самом внутреннем цикле вы выполняете рекурсию f(i) для каждого x но f(i) одинаково для всех x. Это вызывает много избыточной обработки. Всегда переводите вычисления на уровень, который Один = Один, скорее, чем Один = Многие чтобы избежать ненужных накладных расходов.

  Ваш внутренний цикл

for(let i=n; i>=n/2|0; i--){
  if(i==n){
    result.push(n + "+0")
    continue
  }
  for(const x of (f(n-i)||[])) {
    for(const y of (f(i) || [])) { //  repeated call to f(i) 
      result.push(y + "+" + x)
    }
  }
}

Пример вывода рекурсивного вызова из внутреннего цикла

for (let i = n; i >= n / 2 | 0; i--) {
    if (i === n) {
        result.push(n + "+0");
    } else {
        const solvedForI = f(i); // called once only
        for (const x of f(n - i)) {
            for (const y of solvedForI) {
                result.push(y + "+" + x)
            }
        }
    }
}

Советы

Побитовое разделение и пол

С использованием | 0 to floor Numbers — удобный способ сокращения, но вы можете разделить на степень 2 и этаж за одну операцию.

Пример n / 2 | 0 такой же как n >> 1. Каждый сдвиг влево делится на 2, а каждый сдвиг вправо умножается на два.

(n / 2 | 0) === (n >> 1)
(n / 4 | 0) === (n >> 2)
(n / 8 | 0) === (n >> 3)
(n / 256 | 0) === (n >> 8)

• Примечание что преобразование в uint32 происходит до сдвига, поэтому умножение не эквивалентно. Например 1.5 << 1 === 2 а также 1.5 * 2 | 0 === 3

• Примечание Операции Bitwize преобразуются в unsigned int 32 и поэтому должны использоваться только для чисел в диапазоне $ — (2 ^ {31}) $ к $ 2 ^ {31} — 1 $

Кеш

Вы можете использовать кеш для хранения результатов функции. Для рекурсивных функций это может сэкономить много времени на обработку.

Пример псевдокода кеша

Для положительных целочисленных значений вы можете использовать Множество, Для других типов аргументов вы должны использовать карта

// n is a positive integer
function solution(n) {     // wrapper  
    const cache = [];
    return recurser(n);    // call recursive solution.

    function recurser(n) { // n is a positive integer
        var result;
        if (cache[n]) { return cache[n] }  // Return cache if available
        
        while ( ) { 
            ...
            recurser(n - val);

            /* Some complicated code that adds to result */

            ... 
        }

        return cache[n] = result;
    }
}

Сложность, производительность и пример

TL; DR

Следующая часть ответа касается производительности и сложности, а также того, как их можно улучшить с помощью примера функции.

Поскольку пример представляет собой совершенно другой подход, это не считается обзором (переписыванием), однако некоторые из них могут быть использованы в вашем решении.

Сложность

Ваша сложность находится в субэкспоненциальном диапазоне $ O (n ^ {mlog (n)}) $ где $ m $ это какое-то значение> = 2. Это довольно плохо. Пример снижает сложность за счет уменьшения значения $ m $.

Представление

Производительность косвенно связана со сложностью. Вы можете повысить производительность, не меняя сложности. Выигрыш достигается за счет использования более эффективного кода, а не более эффективного алгоритма.

Пример

Пример представляет собой совершенно другой алгоритм, но некоторые методы могут быть применены к вашим решениям, например, кэш и перемещение проверки найденных комбинаций из рекурсивной функции.

Устранение сложности

Я не мог изменить ваш алгоритм, чтобы повысить сложность, это не из-за того, что ваш подход не был менее сложным, а просто потому, что мне не удалось его найти.

Решение проблемы производительности

Есть много возможностей для повышения производительности с помощью кеширования, строк, сортировки и т. Д.

Кеш

В примере используется кеш для сокращения вычислений. См. Выше Советы по поводу кеша.

• Примечание кеш настроен так, чтобы содержать результат n от 0 до 2, что эквивалентно вашим первым 3 операторам if.

Струны

Чтобы избежать дублирования, вы используете Набор и поскольку два массива, содержащие одинаковые значения, не совпадают, вы преобразуете массив в строку, которая может однозначно идентифицировать содержимое массива.

Однако вы манипулируете строками во внутренних циклах и конвертируете из строки в число и обратно на каждой повторной итерации.

Используя подход обертывания рекурсивной функции, мы можем избежать преобразования в основных решениях и использовать набор для фильтрации дубликатов один раз перед возвратом окончательного результата.

Сортировать

Хотя сортировка не является основной частью сложности, я начал с нее, когда делал пример.

Каждая итерация добавляет к создаваемым массивам только одно значение. Поддерживая правильный порядок в процессе сортировки, можно полностью избежать сортировки, и мы просто создаем массив, вставляя новый элемент в правильную позицию.

Самый внутренний for (const v of sub) { Цикл делает это, вставляя новое значение в каждый подмассив, возвращенный предыдущим рекурсивным решением.

Сравнение кода

Чтобы оценить производительность и сложность, я запустил ваш код в качестве основы и использовал его результаты для проверки правильности примеров.

Затем я добавил счетчики для подсчета каждой счетной итерации, в том числе скрытых итераций, таких как те, которые выполняются спредами. ..., отображение массива и обратное преобразование, конкатенация строк, сортировка и т. д.

Результаты следующие

Количество итераций на тест n значение

• Примечание Результаты примера могут выглядеть не так плохо, как n увеличивается, но все еще находится в том же диапазоне сложности $ O (n ^ {mlog (n)}) $. Все, что мне удалось сделать, это ниже $ m $

• Примечание Чтобы соответствовать вашему результату, мне пришлось добавить Array.reverse до финальных комбинаций. Было подсчитано обратное, но это не требуется.

function combos(n) {
    const cache = [[], [[1]], [[2], [1, 1]]];
    return [...(new Set([...combo(n).map(v=>v.reverse().join`+`)]))];

    function combo(n) {
        var a = n - 1, b, insert;
        if (cache[n]) { return cache[n] }

        const res = n % 2 ? [[n]] : [[n], [n >> 1, n >> 1]];
        while (a > n - a) {
            b = n - a;
            for (const sub of combo(a--)) {
                const subRes = [];
                insert = true;
                for (const v of sub) {
                    v > b || !insert ? subRes.push(v) : (insert = false, subRes.push(b, v)); 
                }
                insert && subRes.push(b);
                res.push(subRes);
            }
        }
        return cache[n] = res;
    }
}

• Ваш код работает не очень хорошо, я полагаю, из-за двойной рекурсии внутри f-метод.
• Не хватает читаемость: допустим, вы вернетесь к этому коду через год: сколько времени потребуется, чтобы понять, что вы на самом деле хотели сделать?
• Всегда используйте строгое сравнение равенства (n == 0 => n === 0).

Читаемость можно, по крайней мере, улучшить с помощью интерполяции, использования интервалов / отступов, точек с запятой и скобок. Пропуск точки с запятой может укусить вас.

Отступы и скобки делают код более читабельным. Например:

if(n==0) return ["0"]

лучше читается с интерполяцией:

if (n === 0) {
  return ["0"];
}

Или же:

[...].join`+`

Может работать, но join — это метод Array, поэтому его удобнее использовать [...].join("+")