Улучшен поиск числа N из массива, сумма всех возможных M

JavaScript

Настоящим заявляется, что алгоритм в этой статье изменен с«Найти все возможные N чисел, сумма которых равна M, из массива — лучшее решение»одна статья. Отличие этой статьи в том, что используется двоичное представление положительной последовательности, которое более интуитивно понятно и проще в реализации.

вопрос

Найдите N чисел из массива, сумма которых равна всем возможным M.

Например, выберите 2 элемента из массива [1, 2, 3, 4] и просуммируйте все возможные 5. Ответ два набора комбинаций: 1,4 и 2,3.

Предположим, что функция-оболочкаsearch:

function search(arr, count, sum) {
    ...
    return res
}

тогда есть,

search([1,2,3,4],2,5)
// => [[2,3],[1,4]]

Реализовать идеи

Здесь мы кратко говорим об общей идее: построить бинарные данные по длине массива, а затем выбрать данные, удовлетворяющие условиям.

Мы используем 1 и 0, чтобы указать, выбран ли элемент в массиве. Следовательно, 0110 можно использовать для указания того, что выбраны 1-й и 2-й биты в массиве.

Ниже приведен список всех представлений двоичных данных длины 4:

  • 0000 означает отсутствие элементов в массиве
  • 0001 означает, что выбран 3-й элемент в массиве
  • 0010 означает, что выбран второй элемент в массиве
  • 0011 означает, что выбраны 2-й и 3-й элементы в массиве
  • 0100 означает, что выбран первый элемент в массиве
  • 0101 означает, что выбраны 1-й и 3-й элементы в массиве
  • 0110 означает, что выбраны 1-й и 2-й элементы в массиве
  • 0111 означает, что выбраны 1-й, 2-й и 3-й элементы в массиве
  • 1000 означает, что выбран 0-й элемент в массиве
  • 1001 означает, что выбраны 0-й и 3-й элементы в массиве
  • 1010 означает, что выбраны 0-й и 2-й элементы в массиве
  • 1011 означает, что выбраны 0-й, 2-й и 3-й элементы в массиве
  • 1110 означает, что выбраны 0-й, 1-й и 2-й элементы в массиве
  • 1111 означает, что выбраны все битовые элементы в массиве

Итак, в примере в начале выберите 2 из 4, есть 6 вариантов двоичного кода, удовлетворяющего условиям: 0011, 0101, 0110, 1001, 1010 и 1100. Только 0110 и 1001 соответствуют сумме соответствующих элементов, равной 5.

Видите ли, идея в том, что мы строим все бины длины 4, а затем находим двоичные файлы, удовлетворяющие условиям.

Здесь есть два условия.

  • Во-первых, выбранное число равно 2.
  • Во-вторых, выбранная сумма равна 5.

Наши идеи алгоритма постепенно становятся ясными: Пройдитесь по всем двоичным файлам, определите, равно ли выбранное число 2, а затем найдите сумму соответствующих элементов, чтобы увидеть, равно ли оно 5.

Первый вопрос, как обойти все бинарные данные?

Нас сложно увидеть, длина массива 4, тогда все бинарные данные 0--15.

for (var i = 0; i < 16; i++) {
  ...
}

Длина массива равна 4, что соответствует 16, т.е. 1

Обратите внимание, что 1

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

Способов реализации много, например, один из них:

function n(i) {
  var count = 0;
  while( i ) {
   if(i & 1){
    ++count;
   }
   i >>= 1;
  }
  return count;
}
console.log(n(0b1010))
// => 2

Идея приведенного выше алгоритма на самом деле очень проста, постепенно сдвигаем бинарник вправо на 1 бит, и видим количество единиц в конце. Например, двоичное значение 10 — это 1010, а все возможные сдвиги вправо — это 1010->101->10->1->0, 2 из которых равны 1 в конце. Итак, результат 2.

Третий вопрос, как суммировать на основе бинарных данных?

Например, 0110, мы должны суммировать arr[1] + arr[2].

Вопрос превращается в то, как судить, находится ли индекс массива в 0110?

На самом деле все очень просто, например, индекс 1 есть, а индекса 3 нет. Мы конвертируем 1 в 0100, 0110 и 0100 равны 0100, что больше 0, поэтому индекс 1 присутствует. А 0110 и 0001 равны 0, поэтому нижнего индекса 3 там нет.

Таким образом, суммирование мы можем сделать следующим образом:

var arr = [1,2,3,4]
var s = 0, temp = [];
for (var i = 0, len = arr.length; i < len; i++) {
  if ( 0b0110 & 1 << (len - 1 - i)) {
	s += arr[i]
	temp.push(arr[i])
  }
}
console.log(temp)
// => [2,3]

наконец понял

С приведенным выше предзнаменованием вот окончательная реализация:

function search(arr, count, sum) {
  var len = arr.length, res = [];
  for (var i = 0; i < Math.pow(2, len); i++) {
	if (n(i) == count) {
	  var s = 0, temp = [];
	  for (var j = 0; j < len; j++) {
		if (i & 1 << (len - 1 -j)) {
		  s += arr[j]
		  temp.push(arr[j])
		}
	  }
	  if (s == sum) {
		res.push(temp)
	  }
	}
  }
  return res;
}

function n(i) {
  var count = 0;
  while( i ) {
   if(i & 1){
    ++count;
   }
   i >>= 1;
  }
  return count;
}

console.log(search([1,2,3,4],2,5))
// => [[2,3],[1,4]]

Наконец, видно, что нет необходимости вводить различные понятия, чтобы сделать этот алгоритм понятным.

Эта статья закончилась.

Категории