Медленный и отстающий javascript [дубликат]

Решение этой проблемы было дано миллион раз в Интернете. Задача называется Задача об изменении монет . Можно найти решения в http://rosettacode.org/wiki/Count_the_coins и математическую модель этого в http://jaqm.ro/issues/volume-5,issue-2/ pdf / patterson_harmel.pdf (или проблема с изменением монеты Google ).

Кстати, решение Scala от Tsagadai интересно. В этом примере получается 1 или 0. В качестве побочного эффекта он перечисляет на консоли все возможные решения. Он отображает решение, но не делает его пригодным для использования каким-либо образом.

Чтобы быть как можно полезнее, код должен возвращать List[List[Int]], чтобы разрешить получать количество решений (длина списка списков), «лучшее» решение (самый короткий список) или все возможные решения.

Вот пример. Это очень неэффективно, но это легко понять.

object Sum extends App {

  def sumCombinations(total: Int, numbers: List[Int]): List[List[Int]] = {

    def add(x: (Int, List[List[Int]]), y: (Int, List[List[Int]])): (Int, List[List[Int]]) = {
      (x._1 + y._1, x._2 ::: y._2)
    }

    def sumCombinations(resultAcc: List[List[Int]], sumAcc: List[Int], total: Int, numbers: List[Int]): (Int, List[List[Int]]) = {
      if (numbers.isEmpty || total < 0) {
        (0, resultAcc)
      } else if (total == 0) {
        (1, sumAcc :: resultAcc)
      } else {
        add(sumCombinations(resultAcc, sumAcc, total, numbers.tail), sumCombinations(resultAcc, numbers.head :: sumAcc, total - numbers.head, numbers))
      }
    }

    sumCombinations(Nil, Nil, total, numbers.sortWith(_ > _))._2
  }

  println(sumCombinations(15, List(1, 2, 5, 10)) mkString "\n")
}

При запуске он отображает:

List(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)
List(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2)
List(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2)
List(1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2)
List(1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2)
List(1, 1, 1, 1, 1, 2, 2, 2, 2, 2)
List(1, 1, 1, 2, 2, 2, 2, 2, 2)
List(1, 2, 2, 2, 2, 2, 2, 2)
List(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 5)
List(1, 1, 1, 1, 1, 1, 1, 1, 2, 5)
List(1, 1, 1, 1, 1, 1, 2, 2, 5)
List(1, 1, 1, 1, 2, 2, 2, 5)
List(1, 1, 2, 2, 2, 2, 5)
List(2, 2, 2, 2, 2, 5)
List(1, 1, 1, 1, 1, 5, 5)
List(1, 1, 1, 2, 5, 5)
List(1, 2, 2, 5, 5)
List(5, 5, 5)
List(1, 1, 1, 1, 1, 10)
List(1, 1, 1, 2, 10)
List(1, 2, 2, 10)
List(5, 10)

Функция sumCombinations() может использоваться сама по себе и результат может быть дополнительно проанализирован, чтобы отобразить «лучшее» решение (самый короткий список) или количество решений (количество списков).

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

Например, мы могли бы подумать, что List(5, 10) должен дать две комбинации: List(5, 10) и List(10, 5). Для List(5, 5, 5) он может давать только три комбинации или один, в зависимости от требований. Для целых чисел три перестановки эквивалентны, но если мы имеем дело с монетами, например, в «проблеме смены монет», это не так.

Также не указано в требованиях, является ли вопрос о том, (или монету) можно использовать только один или несколько раз. Мы могли бы (и должны!) Обобщить проблему на список списков вхождений каждого числа. Это переводит в реальной жизни в «каковы возможные способы сделать определенную сумму денег с помощью набора монет (а не набора значений монет)». Первоначальная проблема - только частный случай этого, где у нас столько же вхождений каждой монеты, сколько необходимо, чтобы сделать общую сумму с каждым значением одной монеты.