Создание уникальных отсортированных разделов в Ruby

Question

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

6     
5 1    
4 2    
4 1 1   
3 3    
3 2 1   
3 1 1 1  
2 2 2   
2 2 1 1  
2 1 1 1 1 
1 1 1 1 1 1 

Сейчас я просто сосредотачиваюсь на создании этих множеств, и я пытаюсь сделать это рекурсивно. По сути ... это все последовательности чисел, когда комбайны дадут некоторое общее количество в этом случае. 6. Но обратите внимание, как при первом числе равно 3, число следующих чисел - это просто набор последовательностей, который дает общее количество 3. Иными словами, 6 (общее количество) - 3 (первое число) = 3 (множество последовательностей, которые дают общее число 3). Таким образом, он должен иметь возможность сделать это рекурсивно.

Я пытался кодировать следующим образом (и да, это мой первый язык, и да, я только учился около недели, поэтому я уверен, что все это испортило), но пока не повезло. Я думаю, что если я могу просто получить самое ядро ​​рекурсии, работая и поместив значения всех объектов на экран, чтобы я мог отслеживать их по строкам, я думаю, что могу двигаться вперед, но между логикой и синтаксисом я «У стойки.

Моя логика:

• определить метод, который проходит «количества», представляющее общую мишень.
• создать массив, который будет удерживать заданную последовательность значений.
• создать индекс, который представляет позицию в массиве (игнорируя нулевую позицию).
• определите 'дельта' и инициализируйте его значением 'count' и представляйте оставшуюся целевую сумму остальной части массива. (поскольку вначале ничего нет в массиве, дельта совпадает с числом.)

Затем пройдите через возможности для следующего (первого) значения последовательности, начиная с 1 и заканчивая, очевидно, с максимально возможным, что является значением самого «счета». Определите новую дельта для каждого значения в цикле.

Если дельта равна 0, в противном случае вы определяете эту новую последовательность, которая даст эту новую дельта. Вероятно, необходимо добавить новую последовательность в текущую последовательность.

i=0 

    def seq(count) 
     cvc=Array.new # array to hold the number values 
     i=i+1 # position index for the array 
     puts 'i is ' + i.to_s 
     delta=count 
     puts ' delta is ' + delta.to_s 

     for value in 1..delta do # value represents the number value 
       cvc[i]=value 
       puts 'cvc[i] is ' + cvc[i].to_s 
       delta = delta-cvc.sum 
       puts 'new delta is '+ delta.to_s 
      if delta >1 then count=delta 
        seq(count) 
      end 
     end 
    end 

Answer 1

Вот решение:

def expand(n, max = n) 
    return [[]] if n == 0 
    [max, n].min.downto(1).flat_map do |i| 
    expand(n-i, i).map{|rest| [i, *rest]} 
    end 
end 

expand(6) # => [[6], [5, 1], [4, 2], [4, 1, 1], [3, 3], [3, 2, 1], [3, 1, 1, 1], [2, 2, 2], [2, 2, 1, 1], [2, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1]]