Найдите наборы сумм

15

Мне понравилось читать этот сайт; это мой первый вопрос Редактирование приветствуется.

Для заданных натуральных чисел n и m вычислить все упорядоченные разбиения m на ровно n частей целых положительных целых частей и вывести их, разделенные запятыми и символами новой строки. Любой порядок в порядке, но каждый раздел должен появляться ровно один раз.

Например, если задано m = 6 и n = 2, возможные разбиения - это пары натуральных чисел, сумма которых равна 6:

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

Обратите внимание, что [1,5] и [5,1] являются различными упорядоченными разделами. Вывод должен быть точно в указанном выше формате, с дополнительным завершающим переводом строки. (РЕДАКТИРОВАТЬ: Точный порядок разделов не имеет значения). Вход / выход осуществляется через стандартный код-ввод / вывод для гольфа .

Другой пример вывода для m = 7, n = 3:

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

Наименьший код в байтах после 1 недели выигрывает.

Опять же, отредактируйте, если необходимо.

Приложение:

@TimmyD спросил, какой размер целочисленного ввода должна поддерживать программа. За примерами нет жесткого минимума; действительно, выходной размер увеличивается в геометрической прогрессии, примерно моделируясь: lines = e ^ (0,6282 n - 1,8273).

n | m | lines of output
2 | 1 | 1
4 | 2 | 2
6 | 3 | 6
8 | 4 | 20
10 | 5 | 70
12 | 6 | 252
14 | 7 | 924
16 | 8 | 3432
18 | 9 | 12870
20 | 10 | 48620
22 | 11 | 184756
24 | 12 | 705432
cuniculus
источник
Нужно ли, чтобы ответы поддерживали сколь угодно большие целые числа, или подходящая верхняя граница, например 2 ^ 31-1, подходит?
AdmBorkBork
4
Термин «наборы» сбивает с толку, потому что порядок имеет значение. Я думаю, что термин, который вы ищете, это заказанные перегородки.
xnor
2
Хотя в этом нет необходимости менять, у нас обычно более свободный формат вывода, чем этот.
lirtosiast
Я изменил вашу формулировку, чтобы разрешить ввод-вывод через аргументы функций, приглашения и другие методы ввода-вывода, которые мы обычно считаем приемлемыми.
lirtosiast
@TimmyD, размер вывода растет довольно быстро, так что нецелесообразно пробовать m и n после нескольких сотен, не говоря уже о 2 ^ 31-1.
Куникулус

Ответы:

7

Pyth, 14 байт

V^SQEIqsNQj\,N

Попробуйте онлайн: демонстрация или тестовый набор

Объяснение:

V^SQEIqsNQj\,N   implicit: Q = first input number
  SQ             create the list [1, 2, ..., Q]
    E            read another number
 ^               cartesian product of the list
                 this creates all tuples of length E using the numbers in SQ
V                for each N in ^:
     IqsNQ          if sum(N) == Q:
          j\,N         join N by "," and print
Jakube
источник
Также 14 байт, другой подход: jjL\,fqsTQ^SQE.
PurkkaKoodari
6

Python 3, 77 байт

def f(n,m,s=''):[f(i,m-1,',%d'%(n-i)+s)for i in range(n)];m|n or print(s[1:])

Рекурсивная функция, которая создает каждую выходную строку и печатает ее. Пробует каждое возможное первое число, возвращаясь вниз, чтобы найти решение с соответствующей уменьшенной суммой nи на одно меньшее слагаемое mи префиксом строки sс этим числом. Если и требуемая сумма, и число слагаемых равны 0, мы достигли отметки, поэтому распечатываем результат, обрезая начальную запятую. Это проверяется как m|n0 (Falsey).

79 символов в Python 2:

def f(n,m,s=''):
 if m|n==0:print s[1:]
 for i in range(n):f(i,m-1,','+`n-i`+s)
XNOR
источник
4

CJam, 22 байта

q~:I,:)m*{:+I=},',f*N*

Попробуйте онлайн в интерпретаторе CJam .

Как это устроено

q~                      Read and evaluate all input. Pushes n and m.
  :I                    Save m in I.
    ,:)                 Turn it into [1 ... I].
       m*               Push all vectors of {1 ... I}^n.
         {    },        Filter; for each vector:
          :+I=            Check if the sum of its elements equals I.
                        Keep the vector if it does.
                ',f*    Join all vectors, separating by commas.
                    N*  Join the array of vectors, separating by linefeeds.
Деннис
источник
3

Pyth, 20 18 байтов

-2 байта @Dennis!

jjL\,fqQlT{s.pM./E

Это принимает nкак первую строку ввода, а mв качестве второй.

Попробуй это здесь .

lirtosiast
источник
3

Haskell, 68 байт

n#m=unlines[init$tail$show x|x<-sequence$replicate n[1..m],sum x==m]

Пример использования:

*Main> putStr $ 2#6
1,5
2,4
3,3
4,2
5,1

Как это работает: sequence $ replicate n listсоздает все комбинации nэлементов нарисованной формы list. Мы принимаем все такие xиз [1..m]которых sumравно m. unlinesи init$tail$showсоздайте требуемый формат вывода.

Ними
источник
3

Dyalog APL , 33 байта

{↑1↓¨,/',',¨⍕¨↑⍺{⍵/⍨⍺=+/¨⍵},⍳⍵/⍺}

Принимает mкак левый аргумент, nкак правый аргумент.

Почти половина (между {и ) предназначена для необходимого форматирования.

Адам
источник
2

Mathematica, 65 байт

StringRiffle[Permutations/@#~IntegerPartitions~{#2},"
","
",","]&

IntegerPartitionsделает задачу Остальное просто заказать кортежи и отформатировать результат.

LegionMammal978
источник
2

Питон 3, 112

from itertools import*
lambda m,n:'\n'.join(','.join(map(str,x))for x in product(range(m),repeat=n)if sum(x)==m)

Я не управлял 1 лайнером некоторое время. :)

Морган Трепп
источник
1

Python 2,7, 174 170 152 байта

Тучный ответ. По крайней мере, это читабельно :)

import sys,itertools
m=int(sys.argv[1])
for k in itertools.product(range(1,m),repeat=int(sys.argv[2])):
    if sum(k)==m:print str(k)[1:-1].replace(" ","")
Габриэле д'Антона
источник
Вы можете удалить пробелы вокруг >, после replaceи после запятой.
Алекс А.
1

Юлия, 105 байт

f(m,n)=for u=∪(reduce(vcat,map(i->collect(permutations(i)),partitions(m,n)))) println("$u"[2:end-1])end

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

Ungolfed:

function f(m::Integer, n::Integer)
    # Get the integer partitions of m of length n
    p = partitions(m, n)

    # Construct an array of all permutations
    c = reduce(vcat, map(i -> collect(permutations(i)), p))

    # Loop over the unique elements
    for u in unique(c)
        # Print the array representation with no brackets
        println("$u"[2:end-1])
    end
end
Алекс А.
источник
0

Perl 6 , 54 байта

Если бы вывод мог быть списком списков

{[X] (1..$^m)xx$^n .grep: $m==*.sum} # 36 bytes
my &code = {[X] (1..$^m)xx$^n .grep: $m==*.sum}
say .join(',') for code 7,3;

То, как это в настоящее время сформулировано, я должен добавить joinв лямбду.

{say .join(',')for [X] (1..$^m)xx$^n .grep: $m==*.sum} # 54 bytes
{...}( 7,3 );
1,1,5
1,2,4
1,3,3
1,4,2
1,5,1
2,1,4
2,2,3
2,3,2
2,4,1
3,1,3
3,2,2
3,3,1
4,1,2
4,2,1
5,1,1
Брэд Гилберт b2gills
источник