Найти все возможные комбинированные (плюс и минус) суммы n аргументов? - PullRequest
Новая
       59

Найти все возможные комбинированные (плюс и минус) суммы n аргументов?

7 голосов
/ 02 июля 2019

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

Функция принимает n входных данных и вычисляет все возможные суммы сложения и вычитания, например, если аргументы равны 1,2,3

1 + 2 + 3
1 - 2 - 3
1 + 2 - 3
1 - 2 + 3

Наконец, функция выводит ближайшую суммув ноль.В этом случае ответом будет просто 0.

У меня много проблем с выяснением того, как зациклить n аргументов, чтобы использовать все возможные комбинации операторов + и -.

Мне удалось построить функцию, которая либо добавляет все, либо вычитает все переменные, но я застрял на том, как подходить к различным + и -, особенно при рассмотрении нескольких возможных переменных.

var sub = 0;
var add = 0;

function sumAll() {
  var i;

  for (i = 0; i < arguments.length; i++) {
    sub -= arguments[i];
  }
  for (i = 0; i < arguments.length; i++) {
    add += arguments[i];
  }
  return add;
  return sub;
};
console.log(add, sub); // just to test the outputs

Я хотел бы рассчитать все возможные расположения + и - для любого заданного числа входов (всегда целые числа, как положительные, так и отрицательные).Приветствуются предложения по сравнению сумм с нулем, хотя я еще не пробовал и лучше попробую, прежде чем спрашивать об этом.Спасибо.

Ответы [ 5 ]

2 голосов
/ 02 июля 2019

Я бы перебрал возможные биты числа.Например, если есть 3 аргумента, то есть 3 бита, и наибольшее число, представляемое этими битами, равно 2 ** 3 - 1 или 7 (когда установлены все 3 бита, 111 или 1 + 2 + 4).Затем выполните итерацию от 0 до 7 и проверьте, установлен ли каждый битовый индекс.

Например, на первой итерации, когда число равно 0, биты равны 000, что соответствует +++- добавьте все 3 аргумента вверх.

На второй итерации, когда число равно 1, биты равны 001, что соответствует -++, поэтому вычтите первый аргумент и добавьте два других аргумента.

Третья итерация будет иметь 2, или 010, или +-+.

Третья итерация будет иметь 3, или 011, или +--.

Третья итерация будет иметь 4, или 100, или -++.

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

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

const sumAll = (...args) => {
  const limit = 2 ** args.length - 1; // eg, 2 ** 3 - 1 = 7
  let totalClosestToZeroSoFar = Infinity;
  for (let i = 0; i < limit; i++) {
    // eg '000', or '001', or '010', or '011', or '100', etc
    const bitStr = i.toString(2).padStart(args.length, '0');
    let subtotal = 0;
    console.log('i:', i, 'bitStr:', bitStr);
    args.forEach((arg, bitPos) => {
      if (bitStr[args.length - 1 - bitPos] === '0') {
        console.log('+', arg);
        subtotal += arg;
      } else {
        console.log('-', arg);
        subtotal -= arg;
      }
    });
    console.log('subtotal', subtotal);
    if (Math.abs(subtotal) < Math.abs(totalClosestToZeroSoFar)) {
      totalClosestToZeroSoFar = subtotal;
    }
  }
  return totalClosestToZeroSoFar;
};

console.log('final', sumAll(1, 2, 3));

Вы можете "упростить", заменив [args.length - 1 - bitPos] на [bitPos] для того же результата, но это будет выглядеть немного более запутанным - например, 3 (011, или +--), станет 110 (--+).

Это намного короче без всех журналов, которые демонстрируют, что код работает должным образом: 

const sumAll = (...args) => {
  const limit = 2 **  args.length - 1;
  let totalClosestToZeroSoFar = Infinity;
  for (let i = 0; i < limit; i++) {
    const bitStr = i.toString(2).padStart(args.length, '0');
    let subtotal = 0;
    args.forEach((arg, bitPos) => {
      subtotal += (bitStr[bitPos] === '0' ? -1 : 1) * arg;
    });
    if (Math.abs(subtotal) < Math.abs(totalClosestToZeroSoFar)) {
      totalClosestToZeroSoFar = subtotal;
    }
  }
  return totalClosestToZeroSoFar;
};

console.log('final', sumAll(1, 2, 3));

Вы можете сократить количество операций вдвое, произвольно выбрав знак для первой цифры.Например.в настоящее время с sumAll(9, 1) оба ответа 8 (9 - 1) и -8 (1 - 9) будут действительны, потому что они оба одинаково близки к 0. Независимо от ввода, если +- производит число, ближайшее к 0, затем -+ также, только с противоположным знаком.Точно так же, если ++--- выдает число, близкое к 0, то --+++ также с противоположным знаком.Выбирая знак для первой цифры, вы можете заставить расчетный результат иметь только один знак, но это не повлияет на расстояние результата алгоритма от 0.

Это немногоулучшения (например, 10 аргументов, 2 ** 10 - 1 -> 1023 итерации улучшаются до 2 ** 9 - 1 -> 511 итераций), но это нечто. 

const sumAll = (...args) => {
  let initialDigit = args.shift();
  const limit = 2 **  args.length - 1;
  let totalClosestToZeroSoFar = Infinity;
  for (let i = 0; i < limit; i++) {
    const bitStr = i.toString(2).padStart(args.length, '0');
    let subtotal = initialDigit;
    args.forEach((arg, bitPos) => {
      subtotal += (bitStr[bitPos] === '0' ? -1 : 1) * arg;
    });
    if (Math.abs(subtotal) < Math.abs(totalClosestToZeroSoFar)) {
      totalClosestToZeroSoFar = subtotal;
    }
  }
  return totalClosestToZeroSoFar;
};

console.log('final', sumAll(1, 2, 3));
1 голос
/ 02 июля 2019

Это также известно как вариация проблемы разбиения , при которой мы ищем минимальную разницу между двумя частями, на которые мы разделили аргументы (например, разница между [1,2]и [3] равен нулю).Вот один из способов перечислить все различия, которые мы можем создать, и выбрать самые маленькие: 

function f(){
  let diffs = new Set([Math.abs(arguments[0])])
  for (let i=1; i<arguments.length; i++){
    const diffs2 = new Set
    for (let d of Array.from(diffs)){
      diffs2.add(Math.abs(d + arguments[i]))
      diffs2.add(Math.abs(d - arguments[i]))
    }
    diffs = diffs2
  }
  return Math.min(...Array.from(diffs))
}

console.log(f(5,3))
console.log(f(1,2,3))
console.log(f(1,2,3,5))
1 голос
/ 02 июля 2019

Требование к переменному аргументу не имеет отношения к алгоритму, который кажется основным вопросом.Вы можете использовать синтаксис распространения вместо arguments, если хотите.

Что касается алгоритма, если номера параметров могут быть положительными или отрицательными, хорошее место для начала - наивноеАлгоритм перебора О (2 n ).Для каждого возможного местоположения операции мы добавляем знак плюс в этом месте и отдельно добавляем знак минус.На обратном пути к дереву вызовов выберите тот, который в конечном итоге привел к уравнению, которое было ближе всего к нулю.

Вот код: 

const closeToZero = (...nums) =>
  (function addExpr(nums, total, i=1) {
    if (i < nums.length) {
      const add = addExpr(nums, total + nums[i], i + 1);
      const sub = addExpr(nums, total - nums[i], i + 1);
      return Math.abs(add) < Math.abs(sub) ? add : sub;
    }
    
    return total;
  })(nums, nums[0])
;

console.log(closeToZero(1, 17, 6, 10, 15)); // 1 - 17 - 6 + 10 + 15

Теперь вопрос в том, выполняет ли это дополнительную работу.Можем ли мы найти перекрывающихся подзадач ?Если это так, мы можем запомнить предыдущие ответы и посмотреть их в таблице.Отчасти проблема заключается в отрицательных числах: неясно, как определить, приближаемся ли мы к цели или удаляемся от нее, основываясь на подзадаче, которую мы уже решили для данного фрагмента массива.

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

0 голосов
/ 02 июля 2019

Мне нравится присоединиться к этой загадке:)

проблема может быть описана как f n = f n - 1 + a n * x n , где x имеет X и a 0 , ..., n имеет {- 1, 1}

Для одного случая: X * A = y

Для всех случаев X (*) TA = Y, TA = [A n! , ..., A 0 ]

Теперь у нас есть n! разные A 

//consider n < 32
// name mapping TA: SIGN_STATE_GENERATOR, Y: RESULT_VECTOR, X: INPUT    


const INPUT = [1,2,3,3,3,1]
const SIGN_STATE_GENERATOR = (function*(n){
       if(n >= 32) throw Error("Its working on UInt32 - max length is 32 in this implementation")
       let uint32State = -1 >>> 32-n;
       while(uint32State){
          yield uint32State--;
       }
})(INPUT.length)

const RESULT_VECTOR = []
let SIGN_STATE = SIGN_STATE_GENERATOR.next().value
while (SIGN_STATE){
  RESULT_VECTOR.push(
    INPUT.reduce(
      (a,b, index) => 
      a + ((SIGN_STATE >> index) & 1 ? 1 : -1) * b,
      0
    )
  )
  SIGN_STATE = SIGN_STATE_GENERATOR.next().value
}
console.log(RESULT_VECTOR)
0 голосов
/ 02 июля 2019

Я потратил время на работу над способностью, поэтому применяю знаки между каждым элементом в массиве. Это похоже на самый естественный подход ко мне. 

const input1 = [1, 2, 3]
const input2 = [1, 2, 3, -4]
const input3 = [-3, 6, 0, -5, 9]
const input4 = [1, 17, 6, 10, 15]

const makeMatrix = (input, row = [{ sign: 1, number: input[0] }]) => {
  if(row.length === input.length) return [ row ]
  const number = input[row.length]
  return [
    ...makeMatrix(input, row.concat({ sign: 1, number })),
    ...makeMatrix(input, row.concat({ sign: -1, number }))
  ]
}

const checkMatrix = matrix => matrix.reduce((best, row) => {
  const current = {
    calculation:  row.map((item, i) => `${i > 0 ? item.sign === -1 ? "-" : "+" : ""}(${item.number})`).join(""),
    value: row.reduce((sum, item) => sum += (item.number * item.sign), 0)
  }
  return best.value === undefined || Math.abs(best.value) > Math.abs(current.value) ? current : best
})

const processNumbers = input => {
  console.log("Generating matrix for:", JSON.stringify(input))
  const matrix = makeMatrix(input)
  console.log("Testing the following matrix:", JSON.stringify(matrix))
  const winner = checkMatrix(matrix)
  console.log("Closest to zero was:", winner)
}
processNumbers(input1)
processNumbers(input2)
processNumbers(input3)
processNumbers(input4)
...