Calculate the partitions of N
Pyth, 18 bytes
L?b{SM+R-bsdsyMb]Y
Try it online! (The y
at the end is used to call the function)
This is fairly quick.
This uses recursion. If the input is b
, my method will generate the partitions from 0
to b-1
, and then generate the correct partitions from each.
For example, when b=4
:
b=0
gives[[]]
b=1
gives[[1]]
b=2
gives[[2], [1, 1]]
b=3
gives[[3], [1, 2], [1, 1, 1]]
Then, to each partition in b=0
, append 4
(to make the sum 4); to each partition in b=1
, append 3
(to make the sum 4
); etc.
This is mainly how it works.
L?b{SM+R-bsdsyMb]Y
L define a function called "y" which takes an argument: "b"
?b test for truthiness of b (in this case, test if b>0).
{SM+R-bsdsyMb if truthy:
yMb call this function from 0 to b-1.
s unpack each list of partitions, generating only partitions.
+R to each partition (d), append:
- the difference of
b b (the argument) and
sd the sum of d (the partition).
SM sort each partition.
{ remove duplicates.
]Y if falsey:
Y yield [].
] yield [[]].
Pyth, 10 9 bytes
{SMlMM./U
Not too sure if this isn't cheating, but the rules only said one cannot use integer partition (it's not stated clearly in the question itself, but a comment by OP in the question says integer partition). I'm using string list partition, which makes slices of the list that concatenate up to the "mother" list. I believe I have to thank @Maltysen for the idea of using lists rather than strings.
n=15 takes less than one second on my machine.
In dataflow pseudocode:
input // initial data
U range // makes a list of length equal to input
./ partition // partitions string
lMM length // length of each substring in each way to partition
SM sort // sort each way to partition
{ deduplicate // removes all duplicate after sorting
print // implicit, output final result
Try it online here.
MATL, 20 bytes
:"0Gq:@XNG3$Yc!dS!Xu
Try it online!
For input 15
it takes about 2 seconds in the online compiler.
Explanation
This works by generating partition points and then converting to partition lengths. What I mean by this is the following. Given input N = 5, a possible partition is [2 2 1]. This is represented by partition points [0 2 4 5], such that consecutive differences (or lengths) of the partition points give the resulting partition of the input number.
All arrays of partition points start with 0 and end with N. The number k of intermediate points varies from 0 to N-1. For N and k given, the intermediate points can be generated as a combination of the numbers [1, 2, ..., N-1] taken k at a time.
Several arrays of partition points may give rise to the same result in a different order. For example, partition points [0 1 3 5] would give the partition lengths [1 2 2], i.e. the same as the previous [2 2 1] only in a different order. This has to be taken into account by sorting each array of partition lengths and removing duplicates.
: % Implicitly input N. Push [1 2 ... N]. These are the possible values of k,
% except with N instead of 0
" % For each
0 % Push 0
Gq: % Push [1 ... N-1]. These the possible intermediate points
@XN % Push k and produce the combinations. Each k produces a 2D array with
% each combination on a row. The value k=N produces an empty array
G % Push N
3$Yc % Prepend a column of zeros and append a column of N to the array
!d % Transpose. Consecutive differences of each column
S! % Sort each column. Transpose
Xu % Keep only unique rows
% Implicitly end for and display all arrays in the stack