Задача состоит в том, чтобы перечислить все упорядоченные разбиения (состав (комбинаторика)) заданного положительного целого числа n. Эти списки чисел от 1к nкоторой сумма n. Например, при заданном входе n = 4результат должен быть:

4
1, 3
3, 1
2, 2
2, 1, 1
1, 2, 1
1, 1, 2
1, 1, 1, 1

Результат может быть в любом порядке, но должен содержать каждый заказанный раздел один раз. Это означает , что для n = 4, [1, 1, 2], [1, 2, 1]и [2, 1, 1]все должны быть частью результата.

Вот мой собственный код JavaScript, который достигает этого:

function range(n) {
    for (var range = [], i = 0; i < n; range.push(++i));
    return range;
}

function composition(n) {
    return n < 1 ? [[]] : range(n).map(function(i) {
        return composition(n - i).map(function(j) {
            return [i].concat(j);
        });
    }).reduce(function(a, b) {
        return a.concat(b);
    });
}

Golf6, ES6 ( 169 167 119 109 105 89 85 байт ):

n=>n?[].concat(...[...Array(n)].map((x,i)=>i+1).map(b=>m(n-b).map(a=>[b,...a]))):[[]]

Pyth, 7 6 байтов

7-байтовое решение:

Pyth имеет встроенное целочисленное разбиение ./, поэтому 5 из 7 байтов получают порядки.

{s.pM./

Попробуйте онлайн!

Объяснение:

     ./  Integer partition (sorted by default)
  .pM    get all the orderings of each of the partitions as a nested list of lists of orderings
 s       Flatten by one layer
{        Remove duplicates

6-байтовое решение:

Если у вас есть список, ./будет рассчитывать с заказами; Осталось только снова составить номера списков.

lMM./m

Попробуйте онлайн!

Объяснение:

     m  Get lists by gathering a list of [0, 1,...input] (I could use U as well)

   ./   Partition with orderings
 MM     Map an operation across each of the orderings lists of elements
l       where that operation is the length of the sublists

Haskell, 37 байт

f 0=[[]]
f n=[a:x|a<-[1..n],x<-f$n-a]

xnor сохранил два байта.

Python, 56 байт

f=lambda n:[x+[n-i]for i in range(n)for x in f(i)]or[[]]

Рекурсивное решение: Заказанные разбиения nявляются разбиением некоторых небольшим iс 0<=i<nпоследующим остатком в n-iкачестве последнего элемента. Для базового случая n=0имеет только пустой раздел.

Python 2, 61 байт

f=lambda n,s='1,':1/n*[eval(s)]or f(n-1,'1+'+s)+f(n-1,'1,'+s)

Это не самый короткий, но мне очень нравится метод, потому что он такой странный.

Рекурсивно генерирует и оценивает 2**(n-1)строки, такие как

1+1+1+1,
1,1+1+1,
1+1,1+1,
1,1,1+1,
1+1+1,1,
1,1+1,1,
1+1,1,1,
1,1,1,1,

для n=4. Эти строки оцениваются как кортежи, представляющие все разделы. Между любыми двумя единицами есть или +, объединяющий их в одно число, или ,, разделяющий соседние секции.

JavaScript (Firefox 30-57), 63 байта

f=n=>n?[for(i of Array(n).keys())for(a of f(i))[n-i,...a]]:[[]]

Mathematica, 40 байт

Join@@Permutations/@IntegerPartitions@#&

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

CJam , 17 14 байтов

ri"X)"m*{~]p}/

Попробуйте онлайн!

объяснение

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

Это по-прежнему основано на идее, что мы можем выбирать nвремя между добавлением a 1к текущему разделу или увеличением последнего элемента текущего раздела. В этом решении мы делаем это путем генерации 2 ^n-1 различных программ, которые соответствуют этим различным вариантам.

ri      e# Read input and convert to integer N.
        e# Decrement.
"X)"m*  e# Get all strings of length N which consist of 'X' and ')'. If
        e# we treat these strings as CJam code then 'X' pushes a 1 and ')'
        e# increments the top of the stack.
        e# Note that some of these strings will begin with an increment that
        e# doesn't have anything on the stack to work with. This will result in
        e# an error and terminate the program. Luckily, the programs are ordered
        e# such that all programs starting with 'X' are first in the list, so
        e# we get to print all the 2^(N-1) permutations before erroring out.
{       e# For each of these programs (well for the first half of them)...
  ~     e#   Evaluate the string as CJam code. This leaves the partition as
        e#   individual integers on the stack.
  ]p    e#   Wrap the stack in a list and pretty-print it.
}/

Желе , 7 6 байт

-1 байт благодаря @Dennis (конвертировать из унарного ḅ1, а не по сумме для каждого для каждого S€€)

1ẋŒṖḅ1

TryItOnline

Как?

1ẋŒṖḅ1 - Main link: n          e.g. 4
1ẋ     - repeat 1 n times          [1,1,1,1]
  ŒṖ   - partitions of a list     [[[1],[1],[1],[1]], [[1],[1],[1,1]], [[1],[1,1],[1]],
                                   [[1],[1,1,1]],     [[1,1],[1],[1]], [[1,1],[1,1]],
                                   [[1,1,1],[1]],     [[1,1,1,1]]]
    ḅ1 - from base 1 (vectorises)  [[1,1,1,1],        [1,1,2],         [1,2,1],
                                   [1,3],             [2,1,1],         [2,2],
                                   [3,1],             [4]]

Чистый Баш, 51

Это порт блестящего ответа @ xnor , использующего несколько уровней расширений bash для достижения желаемого результата:

a=$[10**($1-1)]
eval echo \$[${a//0/{+,']\ $[}1'}],

Ideone.

• Первая строка - это просто арифметическое расширение для создания переменной, $aсодержащей нули, 1за которыми следуют n-1нули.
• Первое расширение ${a//0/{+,']\ $[}1'}заменяет каждое 0в $aкопиями строки {+,']\ $[}1'. Таким образом, n = 4, мы получаем строку1{+,']\ $[}1'{+,']\ $[}1'{+,']\ $[}1'
• Это с префиксом $[и постфиксом, ],чтобы дать$[1{+,']\ $[}1'{+,']\ $[}1'{+,']\ $[}1]
• Это расширение скобки, которое расширяется до $[1+1+1+1], $[1+1+1] 1, $[1+1] $[1+1], $[1+1] 1 1,...
• Это, наконец, арифметически расширен, чтобы дать требуемый результат.

Тщательное использование кавычек, экранирование от обратной косой черты и evalгарантирует, что расширения происходят в правильном порядке.

Рубин, 61 байт

f=->n{n<1?[[]]:(1..n).map{|i|f[n-i].map{|x|x<<i}}.flatten(1)}

ungolfed

f=->n{
  n < 1 ?
    [[]]
  :
    (1..n).map { |i|
      f[n-i].map { |x|
        x << i
      }
    }.flatten(1)
}

использование

p f[4]
# => [[1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [1, 3], [2, 1, 1], [2, 2], [3, 1], [4]]

Брахилог , 20 байт

~lL#++?,L:=f:{:0x}ad

Попробуйте онлайн!

объяснение

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

~lL                     L is a list of length Input
  L#+                   L is a list of non-negative integers
  L  +?,                The sum of the elements of L results in the Input
        L:=f            Find all values for the elements of L which satisfy those constraints
            :{:0x}a     Remove all 0s from each sublist of the result of Findall
                   d    Remove all duplicate sublists

CJam , 19 байтов

Lari{_1af.+1@f+|}*p

Попробуйте онлайн!

объяснение

CJam не имеет полезной встроенной комбинаторики для целочисленных разделов. Поэтому мы сделаем это вручную. Чтобы найти все упорядоченные разделы целого числа n, мы можем посмотреть список из nних и рассмотреть все возможные способы вставки разделителей. Тогда мы будем суммировать 1s в каждом разделе. Пример для n = 3:

1 1 1 => 3
1 1|1 => 2|1
1|1 1 => 1|2
1|1|1 => 1|1|1

Я попытался использовать декартово произведение для генерации всех этих разделителей, но в итоге получилось 21 байт. Вместо этого я вернулся к этому старому способу генерации наборов мощности (он основан на старом ответе Денниса, но я не могу найти его сейчас). Идея такова: для генерации всех разделов мы можем начать с пустого списка. Затем nмы можем принять двоичное решение: либо мы добавляем 1(соответствует разделителю в приведенном выше примере), либо увеличиваем последнее значение в списке (соответствует отсутствию разделителя). Чтобы сгенерировать все разделы, мы просто выполняем обе операции на каждом шаге и сохраняем все возможные выходные данные для следующего шага. Оказывается, в CJam добавление и добавление первого элемента короче, но принцип остается тем же:

La       e# Push [[]] onto the stack. The outer list will be the list of
         e# all possible partitions at the current iteration, and we initialise
         e# it to one empty partition (basically all partitions of 0).
ri       e# Read input and convert to integer N.
{        e# Repeat this N times...
  _      e#   Duplicate the list of partitions of i-1.
  1af.+  e#   Increment the first element in each of these. This is done
         e#   by performing a pairwise addition between the partition and [1].
         e#   There is the catch that in the first iteration this will turn
         e#   the empty array into [1], so it's equivalent to the next step.
  1@f+   e#   Pull up the other copy of the list of partitions of i-1 and
         e#   prepend a 1 to each of them.
  |      e#   Set union. This gets rid of the duplicate result from the first
         e#   iteration (in all other iterations this is equivalent to concatenating
         e#   the two lists).
         e#   Voilà, a list of all partitions of i.
}*
p        e# Pretty-print the result.

T-SQL, 203 байта

Golfed:

USE master
DECLARE @ INT=12

;WITH z as( SELECT top(@)cast(number+1as varchar(max))a FROM spt_values WHERE'P'=type),c as(SELECT a*1a,a b FROM z UNION ALL SELECT c.a+z.a,b+','+z.a FROM c,z WHERE c.a+z.a*1<=@)SELECT b FROM c WHERE a=@

Ungolfed:

USE master --needed to make sure it is executed from the correct database
DECLARE @ INT=12

;WITH z as
(
  SELECT top(@)cast(number+1as varchar(max))a
  FROM spt_values
  WHERE'P'=type
),c as
(
  SELECT a*1a,a b
  FROM z
  UNION ALL
  SELECT c.a+z.a,b+','+z.a
  FROM c,z
  WHERE c.a+z.a*1<=@
)
SELECT b 
FROM c
WHERE a=@

скрипка

Mathematica 10,0, 44 байта

Попытка без использования встроенных разделов. Из каждого упорядоченного раздела размера k генерируются два последующих раздела k + 1 : один с добавлением 1, а другой путем увеличения первого значения.

Nest[##&[{1,##},{#+1,##2}]&@@@#&,{{1}},#-1]&

Более смешной, но, к сожалению, на 2 байта более длинный способ реализации той же идеи:

#@{1}&/@Tuples[Prepend[1]@*MapAt[#+1&,1],#-1]&

05AB1E , 14 12 байт

Сохранено 2 байта благодаря Аднану

>G¹LNãvyO¹Q—

объяснение

>G              # for N in range(1..input)
  ¹L            # range(1, input)
    Nã          # cartesian product with N (all combinations of length N)
      v         # for each resulting list
       yO¹Q—    # if it's sum equals the input print it

Попробуйте онлайн!

Соответствующее решение на 2 байта короче на 2sable .

2sable , 10 байт

>GLNãvyOQ—

Попробуйте онлайн!

Haskell, 41 байт

f 1=[[1]]
f n=do a:b<-f$n-1;[1:a:b,a+1:b]

Не самое короткое решение на Haskell, но мне нравится, что оно не использует [..]диапазоны. Вместо этого он рекурсивно вычисляет разделы nкак разделы n-1либо с новым 1 в начале, либо с первым более высоким значением. Это ясно дает понять, почему они есть 2^(n-1).

Mathematica, 53 байта

Не IntegerPartitionsпревосходит ответ Мартина Эндера, который использует встроенную функцию (а встроенные функции меня вполне устраивают). (И при этом это не бьет ответ feersum, который я не видел слишком поздно.) Но я хотел практиковать рекурсивную функцию игры в гольф.

If[#<1,{{}},Join@@Table[#~Append~j&/@#0[#-j],{j,#}]]&

Рекурсивно генерирует все композиции, генерируя все возможные конечные числа jи затем вызывая себя, #-jгде #находится ввод.

Сетчатка , 32 байта

Число байтов предполагает кодировку ISO 8859-1.

.+
$*
+%1`1
!$'¶$`,!
!+
$.&
A`^,

Попробуйте онлайн!

объяснение

Это работает аналогично моему ответу CJam . Мы просматриваем список Nи в каждой позиции принимаем обе ветви двоичного решения: а) увеличиваем последнее значение или б) начинаем новое значение с 1.

Этап 1

.+
$*

Преобразовать ввод в унарный.

Этап 2

+%1`1
!$'¶$`,!

+Говорит Retina , чтобы выполнить этот этап в цикле , пока выход не перестанет изменяться. Он %говорит, что нужно разделить ввод на строки перед применением сцены и затем соединить их вместе. Помещая %после +, Retina разделяется и возвращается после каждой итерации. Одна итерация этапа принимает одно из упомянутых мною решений и тем самым раздваивает текущий набор разделов.

Как это работает на самом деле, так это то, что он соответствует 1(но только первому, как указано 1перед обратным трюком) и заменяет его на !(который мы будем использовать в качестве унарной цифры нашего вывода), за которым следуют оставшиеся 1s в этой строке (это увеличивает последнее значение). Затем в другой строке ( ¶) он печатает префикс текущей строки, затем следует ,!, который вставляет разделитель и затем начинает следующее значение в 1.

Этап 3

!+
$.&

Это преобразует ряды !в десятичные целые числа, заменяя их длиной.

Этап 4

A`^,

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

Perl, 44 байта

Включает +3 для -n(код использует $'и $0поэтому не может быть запущен как -eкомандная строка)

Дайте номер разделу на STDIN:

partitions.pl <<< 4

partitions.pl

#!/usr/bin/perl -n
$_=$&-$_.",$_$'",do$0for/\d+/..$&-1;print

Если вы не возражаете против лишних пробелов в конце строки и дополнительной новой строки, это 42-байтовое решение также работает (запустите как perl -M5.010 partitions.pl):

#!/usr/bin/perl -n
$_=$`-$_." $_ $'",do$0for/\s/..$_-1;say

Юлия, 113 байт

f(N)=unique(reduce(vcat,(map(x->[permutations(x)...],[vcat([1 for _=i+1:N],sum([1 for _=N-i:N-1])) for i=1:N]))))

Нерекурсивное решение

Разъяснение:

1. [vcat([1 for _=i+1:N],sum([1 for _=N-i:N-1])) for i=1:N] построить набор списков с суммой N, перестановки которых будут напоминать решение (например, для N = 4: [[1,1,1,1], [1,1,2], [1,3], [4] ]])
2. map(x->[permutations(x)...],) Рассчитать все перестановки
3. reduce(vcat,) объединить их в список списков
4. unique() фильтрация дубликатов

MATL , 15 байт

:"G:@Z^t!XsG=Y)

Попробуйте онлайн!

объяснение

Учитывая входные данные n, это вычисляет декартову силу с увеличением показателей kот 1до n; и для каждого показателя kвыбирает кортежи, которые имеют сумму, равную входным.

:       % Take input n implicitly and push range [1 2 ... n]
"       % For each k in that range
  G:    %   Push [1 2 ... n] again
  @     %   Push k
  Z^    %   Cartesian power. Gives 2D array, say A, with each k-tuple in a row.
  t     %   Duplicate
  !     %   Transpose
  Xs    %   Sum of each column. Gives a row vector
  G=    %   True for entries that equal the input
  Y)    %   Use as logical vector into the rows of array A
        % End implicitly
        % Display stack implicitly

Lua 214 203 182 байта

function g(m, l, n,c)for i=1,m do if i+n < m then l[#l+1]=i;g(m,l,n+i,c+1)elseif i+n == m then l[#l+1]=i;print(unpack(l))end end for k=c,#l do l[k]=nil end end g(io.read()*1,{},0,0)

Раскрытая версия.

function g(m, l, n,c)
    for i=1,m do 
        if i+n < m then 
            l[#l+1]=i
            g(m,l,n+i,c+1)
        elseif i+n == m then 
            l[#l+1]=i
            print(unpack(l))
        end 
    end 
    for k=c,#l do 
        l[k]=nil 
    end 
end 
g(io.read()*1,{},0,0)

Найдены пустые пробелы и удалены ненужные переменные в безопасные 11 байтов. как оказалось, table.insert () неэффективен

PHP, 125 байт

for($i=$n=$argv[1];$i<=str_repeat(1,$n);$i++)if(array_sum($a=str_split($i))==$n&!strpos($i,"0"))$r[]=$a;echo json_encode($r);

-4 байта для print_r($r); вместо вместо echo json_encode($r);для вывода

рекурсивное решение с 250 байтами

function f($n){global$a;foreach($a as$x)foreach(range(1,$n)as$y)$a[]=array_merge((array)$x,[$y]);if(--$n)f($n);}$a=range(1,$w=$argv[1]);f($w-1);foreach($a as$z)if(array_sum((array)$z)==$w)$c[join("-",(array)$z)]=$z;echo json_encode(array_values($c));

Пролог, 81 байт + 6 байт для вызова

L*L.
[H|T]*L:-H>1,M is H-1,[M,1|T]*L.
[H,K|T]*L:-H>1,M is H-1,N is K+1,[M,N|T]*L.

Попробуйте онлайн!
Позвоните [4]*L., повторите, ;пока все решения не будут представлены.

Альтернативно, если многократное нажатие ;не в порядке (или должно быть добавлено к количеству байтов), вызов с bagof(L,[4]*L,M).которым добавляет 17 байтов для вызова.

J , 30 26 байт

#&1<@(+/;.1)~2#:@(+i.)@^<:

Работает, разбивая список унарных n , используя двоичные значения 2 ⁿ .

Попробуйте онлайн!

объяснение

#&1<@(+/;.1)~2#:@(+i.)@^<:  Input: n
                        <:  Decrement n
             2         ^    Compute 2^(n-1)
                 (   )@     Operate on that
                   i.         Make the range [0, 1, ..., 2^(n-1)-1]
                  +           Add 2^(n-1) to each in that range
              #:@           Convert each in that range to binary
#&1                         Make n copies of 1 (n in unary)
     (     )~               Operate over each row on RHS and unary n on LHS
        ;.1                   Chop unary n starting at each 1
      +/                        Reduce by addition on each chop
   <@                           Box the sums of each chop

На самом деле, 17 16 байт

Этот ответ частично основан на ответе Луиса Мендо на MATL . Предложения по игре в гольф приветствуются. Попробуйте онлайн!

;╗R`╜R∙i`M`Σ╜=`░

Ungolfing

         Implicit input n.
;╗       Duplicate n and save a copy of n to register 0.
R        Take the range of [1..n].
`...`M   Map the following function over the range. Variable k.
  ╛R       Push n from register 0 and take the range [1..n] again.
  ∙        Take the k-th Cartesian power of the range.
  i        Flatten that product.
`...`░   Push values of the previous map where the following function returns a truthy value.
          Variable L.
  Σ        Push sum(L).
  ╜        Push n from register 0.
  =        Check if sum(L) == n.
         Implicit return.

На самом деле 17 16 15 байт

Это интересный ответ CJam Мартина Эндера (тот, что содержит декартово произведение), с разницей в реализации, которая, на мой взгляд, была интересной. Когда одна из строк Мартина начинается с приращения, ошибки не позволяют оценить эту строку. На самом деле, ошибка подавляется, и строка все равно оценивается. Это в конечном итоге дает композиции каждогоk в диапазоне[1..n] .

Вместо того, чтобы пытаться удалить лишние композиции, я взял n-1декартову силу "1u"добавления a "1"в начало каждой строки. Этот трюк дает только композиции n. Это, к сожалению, дольше, чем ответ Мартина.

Предложения по игре в гольф приветствуются. Попробуйте онлайн!

D"1u"∙`1@Σ£ƒk`M

Ungolfing

         Implicit input n.
D        Decrement n.
"1u"∙    Take the (n-1)th Cartesian power of the string "1u".
          In Actually, 1 pushes 1 to the stack and u is increment.
`...`M   Map the following function over the Cartesian power. Variable s.
  1@       Push a 1 to be used later.
  Σ        Summing a list of chars joins the chars into one string.
  £ƒ       Turn s into a function and call it immediately on the 1 in the stack.
  k        Take the whole stack and wrap in a list. This is a composition of n.
         Implicit return.