Блог

Главная - Вопросы по программированию - Найти набор чисел, соответствующий числу

Найти набор чисел, соответствующий числу

#ruby

#ruby

Вопрос:

Из числа я хочу сгенерировать разные группы чисел, где сумма соответствует этому числу.

Пример:

 generate_groups([], 1) would be equal to [ [1] ]
generate_groups([], 2) would be equal to [ [1,1] , [2] ]
generate_groups([], 3) would be equal to [ [1, 1, 1], [1, 2], [2, 1], [3] ]

Я уже написал решение в итеративном коде, но есть лучший ответ в рекурсивном.

Итак, я написал следующий код:

 def generate_groups(combo = [], rest)
  return combo.flatten if rest <= 0

  result = []
  (1..rest).each do |number|
    combo << number
    tmp_res = generate_groups(combo, rest-number)
    result << tmp_res
    combo.pop
  end
  return result
end

Но это нехорошо, потому что это генерирует массив в array.
Например, generate_groups([], 3) это: 

 [ [ [ [1, 1, 1] ], [1, 2] ] , [ [2, 1] ] , [3] ]

Что не так в моем алгоритме?

Комментарии:

1. не имеет отношения к вашему алгоритму, но, возможно, быстрый совет ruby: если вы измените аргументы для generate_groups на противоположные, тогда вы можете сделать, чтобы второй был необязательным ( generate_groups(rest, combo=[]) ) для вызова как generate_groups(1) or generate_groups(1, [])

2. @TMP: Это тоже работает так, как есть (начиная с Ruby 2, IIRC).

3. @undur_gongor о, ладно, это круто, я этого не знал. Мне просто показалось странным, что вы указываете пустой массив в своем примере, хотя

Ответ №1:

Ваше решение может быть исправлено следующим образом:

 def generate_groups(combo = [], rest)
  return [combo.dup] if rest <= 0  # no need for flattening 

  result = []
  (1..rest).each do |number|
    combo << number
    tmp_res = generate_groups(combo, rest-number)
    result  = tmp_res # concat the solutions instead of nesting them.
    combo.pop
  end
  return result
end

dup Это необходимо, потому что в противном случае фиксированный результат позже будет изменен путем изменения combo . Ваш flatten также создал копию массива.

Однако передача внутреннего состояния ( combo ) посредством рекурсии выглядит … странно. Это не требуется. Мое предложение

 def generate_groups(rest)
  return [[]] if rest <= 0

  (1..rest).inject([]) do | a, number |
    a   generate_groups(rest - number).map { | g | g << number }
  end
end

С помощью inject я объединяю массивы промежуточных результатов.