| Bytes | Lang | Time | Link |
|---|---|---|---|
| 106 | JavaScript ES12 | 250120T014045Z | Arnauld |
| 044 | Charcoal | 250122T121046Z | Neil |
| 058 | SageMath | 250120T150500Z | Kevin Cr |
| 010 | Nekomata + n | 250121T095619Z | alephalp |
| 080 | Haskell | 250120T072853Z | xnor |
| 111 | Haskell | 250120T051328Z | colossus |
| 255 | Python3 | 250120T005256Z | Ajax1234 |
| 123 | JavaScript Node.js | 250120T021405Z | l4m2 |
| 059 | Retina | 250119T221839Z | Neil |
JavaScript (ES12), 106 bytes
n=>(g=(a,c)=>a[n]?g[c]||=++t:a.map((v,j)=>(h=k=>k&&h(k-1)|g(b=[...a,k],[c,b[j]=v-k,k]))(v>>1)))([t=0,n])|t
Method
We do not need to track the order of values in partitions, nor the positions of the values that are split.
A chain can be uniquely described by the list of pairs \$[v-k,k]\$, where a new pair is added each time a value \$v\$ is split to create the next partition.
In the JS code, we store these pairs as nested arrays in the variable c.
Commented
n => ( // n = input
g = ( // g is a recursive function taking:
a, // a[] = current partition of n
c // c = current chain, initially undefined
) => //
a[n] ? // if the length of a[] is n + 1:
g[c] ||= ++t // if g[c] is not defined, set it and increment t
: // else:
a.map((v, j) => // for each value v at index j in a[]:
( //
h = k => // h is a recursive function taking k
k && // abort if k = 0
h(k - 1) | // otherwise do a recursive call to h with k - 1
g( // do a recursive call to g:
b = [ // define b[] as ...
...a, // a copy of a[] ...
k // ... with k appended
], //
[ // update the chain:
c, // include the previous values
b[j] = // followed by the updated value of b[j] ...
v - k, // ... which is v - k
k // followed by k
] //
) // end of recursive call
)(v >> 1) // initial call to h with k = floor(v / 2)
) // end of map()
)([t = 0, n]) // initial call to g with t = 0 and a = [0, n]
| t // return t
Charcoal, 44 bytes
⊞υ⮌EN¬ιFυF⌕AX⁰ι⁰F⊘⊕κ⊞υEι⁻⁺μ№⟦λ⊖⁻κλ⟧ν⁼νκI№υ⌈υ
Try it online! Link is to verbose version of code. Explanation:
⊞υ⮌EN¬ιFυ
Start a breadth-first search with a list of n-1 0s and a 1 representing the first partition which has 1 n. (Charcoal is actually 0-indexed but I will adjust the indices appropriately.)
F⌕AX⁰ι⁰
Loop over the integers in the current partition.
F⊘⊕κ
Loop over the possible split points for the current integer.
⊞υEι⁻⁺μ№⟦λ⊖⁻κλ⟧ν⁼νκ
Create a new partition that has the count for the original integer decremented and the counts for the two splits incremented. (This works even when the two splits are the same size.)
I№υ⌈υ
Output the number of occurrences of the maximum partition, which will be n followed by n-1 0s representing the final partition of n 1s.
SageMath, 74 58 bytes
lambda n:Posets.IntegerPartitions(n).chain_polynomial()[n]
Taken from the OEIS page and then golfed a bit, so all credit goes to Max Alekseyev.
Explanation:
lambda n: # Lambda with integer argument that returns:
Posets.IntegerPartitions(n) # Get all tuples of positive integers that sum to n
.chain_polynomial() # Get its polynomial formula
[n] # Get the 0-based n'th coefficient
To see each of the intermediate steps separately (for \$n=10\$):
Posets.IntegerPartitions(10): try it online;Posets.IntegerPartitions(10).chain_polynomial(): try it online;- (
Posets.IntegerPartitions(10).chain_polynomial().coefficients(): try it online. Thesecoefficients()is where the.chain_polynomial()[...]will implicitly be indexing into, apparently.)
Nekomata + -n, 10 bytes
řʷ{ĕᵈĕ+coũ
I don't really know why it works. Nekomata's model of nondeterminism is still a mess. I just happened to write the interpreter in a way that it works.
řʷ{ĕᵈĕ+coũ Take n as input
ř Push a list of n copies of n
ʷ{ Loop until failure:
ĕᵈĕ Pick two elements out from the list
Fail if there are not enough elements
+ Add them together
c Prepend the sum back to the list
o Sort
ũ Remove duplicate values of a non-deterministic object
(I'm not entirely sure what this function does in a loop.
It seems it only removes duplicates caused by new
non-deterministic operations in the current iteration.
If two different results of previous iterations give
the same result in the current iteration, this kind of
duplicates will not be removed.)
-n counts the number of solutions.
Haskell, 80 bytes
import Data.List
f l=max 1$sum[f$a:n-a:(l\\[n])|n<-nub l,a<-[1..div n 2]]
f.pure
Recursively tries every possible split of every distinct entry. The nub from Data.List extracts unique elements so a repeated value is only once used as a split, and \\ removes the element being split. The max 1 handles the base case of an unsplittable all-1's list, counting it as 1 rather than 0.
90 bytes
import Data.List
h l=max 1$sum[h$a+b:(l\\[a,b])|a<-nub$l,b<-nub$l\\[a],a<=b]
g n=h$1<$[1..n]
An alternative approach of working upwards, combining pairs. It turned out longer, in part from creating the list of n 1's.
86 bytes
p%(n:t)=sum[f$a:n-a:p++t|all(/=n)p,a<-[1..div n 2]]+(n:p)%t
p%_=0
f=max 1.([]%)
g=f.pure
Based on colossus16's answer, which doesn't use Data.List. It cleverly extracts unique entries without nub by taking only the first appearance of each value, that is one not in the sublist to its left, and using it as a cut point.
My code unrolls the partitioning into a recursive helper function %.
Haskell, 111 bytes
f.pure
f p|all(<2)p=1|1>0=sum[f$a++y:x-y:r|(a,x:r)<-map(`splitAt`p)[0..length p-1],notElem x a,y<-[1..div x 2]]
Basically a brute force method. Values of n above 14 cause TIO to time out.
Python3, 255 bytes
R=range
def f(n):
q,s=[[[1]*n]],[]
for a in q:
if len(a)==n:s+=[a];continue
S,L=[],[*R(len(V:=a[0]))]
for i in L:
for I in R(i+1,len(V)):
if(A:=sorted([V[j]for j in L if j not in[i,I]]+[V[i]+V[I]])) not in S:q+=[[A]+a];S+=[A]
return len(s)
JavaScript (Node.js), 123 bytes
f=(...x)=>x.reduce((s,c,i)=>x[~c]=s+=!x[~c]&&[...Array(c>>1)].reduce((s,_,v)=>s+f(...x.filter(_=>j--,j=i),++v,c-v),0),0)||1
Awful but whatever
Retina, 59 bytes
.+
*
/__/{%Lv$`(?<=(_+))(\1_*)(?<!\1\2.+)
$`.$2$'
)%O`_+
.+
Try it online! Link includes smaller test cases as the code works by generating all chains, which is very slow and memory hungry for larger cases. Explanation:
.+
*
Convert the input to unary, which generates the starting partition.
/__/{`
)`
Repeat while the chains can be extended. (Unfortunately I can't easily use a repeat count as this is 1 less than the input.)
%Lv$`(?<=(_+))(\1_*)(?<!\1\2.+)
$`.$2$'
For each partition, break it at every possible position, and generate the resulting partitions (one for every chain).
%O`_+
Sort each resulting partition back into ascending order.
.+
Count the number of chains found.