Lexicographically Smallest Decreasing Integer Partition

Question

For a given number n, output an strictly decreasing array whose sum is n and its lexicographical order is the smallest for any possible outputs

Smallest lexicographical order means that for or sum n=9 the following strictly decreasing arrays are possible: [[9],[8,1],[7,2],[6,3],[5,4],[6,2,1],[5,3,1],[4,3,2]]. Putting these in lexicographical order: [[4,3,2],[5,3,1],[5,4],[6,2,1],[6,3],[7,2],[8,1],[9]], the first [4,3,2] will be the final output

Testcases

4 -> [3,1]
9 -> [4,3,2]
10 -> [4,3,2,1]
20 -> [6,5,4,3,2]

You may assume that n>0 and that you are allowed to output any human readable form of characters to represent the array of numbers

Note that a strictly decreasing array has no duplicates so the array cannot be [1,1,1...]

This is code-golf, so shortest code wins!

Answer 1

JavaScript (Node.js), 38 bytes

• -7 bytes by att and Bubbler

f=n=>n?[p=.5+(n+n)**.5|0,...f(n-p)]:[]

Try it online!

That is, find out the smallest \$x\$ where

$$ \sum_{i=1}^{x}i= \frac{(x+1)\cdot x}{2}\ge n $$

which is

$$ x=\left\lceil\frac{\sqrt{8n+1}-1}{2}\right\rceil $$

As att and Bubbler suggested in the comments. This formula could be simplified into

$$ x=\left\lfloor\sqrt{2n}+\frac{1}{2}\right\rfloor $$

• att: You don't need the \$+\frac14\$.
• tsh: @att Seems to be correct by testing up to 1e8. But I don't quite understand why. Will there be any proof?
• Bubbler: Rough proof: The change is equivalent to changing 8n+1 to 8n in the second line. There the value of x does not change if the "ceil-to-odd-square" (the smallest odd square number >= input) of 8n+1 is the same as that of 8n. If the value were to change, 8n should be the upper bound of a lower range and therefore an odd square, which is a contradiction.
• Bubbler: Also, this transformation now makes the expression inside ceil always a non-integer, so you can convert it to floor of +1, which gives 38 bytes.

Answer 2

Vyxal, (削除) 7 (削除ここまで) 6 bytes

Ṅ~Þush

Try it Online!

-1 thanks to EmanresuA reminding me that ~ exists.

Explained

Ṅ~Þush
Ṅ # From all integer partitions of the input,
 ~ # Keep only partitions where:
 Þu # The uniqufied version equals the partition (this makes sure that only partitions without duplicates are kept)
 sh # Sort the list and take the first item

• emanresu A: There's a builtin for is_unique :)

Answer 3

Wolfram Language (Mathematica), (削除) 39 (削除ここまで) (削除) 37 (削除ここまで) 32 bytes

<|Tr@#->#&/@Subsets@Range@#|>@#&

Try it online!

Returns the partition in increasing order. For decreasing order, +5 bytes: Try it online!

• theorist: (1) Since the OP asks for a "strictly decreasing array", I think your output for Last@Pick[s=Subsets@Range@#,Tr/@s,#]& needs to be reversed. (2) I didn't know it was permitted to provide an answer in the functional form you gave with f@n_:=#<>f[n-#]&@Round@√(2n) f@0="", so that's good to know. But I don't know whether a StringJoin of integers qualifies as an array.
• att: @theorist I agree on (1), but I felt it was interesting enough to leave be. As for (2), I'm fairly liberal with list output formats, since pretty much any expression with arguments can be interpreted as one; StringJoin is nice to use since it's Flat and <> is short. I do consider List and Sequence to be more "pure" though; we can convert it into Sequence output for 41 bytes.

Answer 4

Pyth, ^{(削除) 19 (削除ここまで) (削除) 16 (削除ここまで) (削除) 13 (削除ここまで) (削除) 11 (削除ここまで)} 10 bytes

hf{ITS_M./

Try it online!

Answer 5

C# (Visual C# Interactive Compiler), 107 bytes

x=>{var y=new List<int>();while(x!=0){y.Add((int)Math.Ceiling((Math.Sqrt(x*8+1)-1)/2));x-=y[^1];}return y;}

Try it online!

I think i can save a few bytes somewhere here, but i can't quite figure it out. Haskell tricks with unrolling multiple arguments comes to mind but it's been too long since i golfed properly to remember it (Lost access to old account when school email expired feelsbad). feel free to improve this and take the points. Uses the same approach as the Javascript answer, but without the JS list comprehension tricks. In other words, find the lowest value such that the sum from 1 to n is greater than x, push that to the list, subtract n from x and repeat until x is 0.

From my early tests, using Floor and the third formula is the same number of characters in C#, though i couldn't really get it working.

This can save a bunch of characters by taking an empty list as a parameter and editing/filling it in place (removes the need for the "new" and the return, effectively making the outer function a one-liner. Further, it could be made recursive, which removes the while loop, though idk if that actually saves anything), but i'd guess that's blocked by loophole rules.

making the list a list of double will save 2 bytes but the results are then doubles, and this raises the possibility of floating point nonsense and potentially printing out 3.0000000004 or something similar.

Edit: Uses the new Index object and it's ^ operator, introduced in C# 8.0. Not normally a fan b/c it makes the code more obtuse, but it's perfect for code golf. ^1 is shorthand for the last element in the list.

• ceilingcat: 103 bytes

Answer 6

05AB1E, 8 bytes

Læí.ΔOQ

Try it online or verify all test cases.

Explanation:

L # Push a sum in the range [1, (implicit) input]
 æ # Pop and get the powerset of this
 # (which is already in the correct order)
 í # Reverse each inner list to make the inner lists in decreasing order
 .Δ # Keep the first inner list that's truthy for:
 O # Where the sum
 Q # Equals the (implicit) input
 # (after which this found result is output implicitly)

Answer 7

Husk, 8 bytes

↔ḟo=1ΣṖḣ

Try it online!

Husk has no 'integer partitions' built-in, but since the array must be strictly decreasing (no duplicates) we can build it by selecting a subset of n..1 that sums to n.
If we do it the other way around (selecting from 1..n), then the first 'hit' is already the right set, and we just need to reverse the order of its elements to make it decreasing.

 ḣ # start with range 1..input:
 Ṗ # get all subsequences;
↔ḟo # now get the first element that satisfies:
 Σ # its sum
 =1 # equals the input;
↔ # and finally reverse it.

Answer 8

Haskell, 45 bytes

f 0=[]
f n=[a:f(n-a)|a<-[1..n],[a]>f(n-a)]!!0

Try it online!

f(n) searches, starting from a = 1 , a list to append to a :

• lexicographically less than a,
  that sums to n (with a).

Such list is f( n-a ).

Answer 9

R, 46 bytes

f=function(n)if(n)c(p<-round((2*n)^.5),f(n-p))

Try it online!

Reproducing tsh resolution in R.

• Dominic van Essen: Nice! You should include the f= as part of the byte count, though, since the name of the function is needed for it to run correctly. Otherwise you can use Recall (like this), but it isn't very golfy...

Answer 10

Factor + math.combinatorics math.unicode, 56 bytes

[ dup 1 [a,b] all-subsets [ Σ = ] with filter infimum ]

Try it online!

• 1 [a,b] all-subsets Powerset of n..1
• dup ... [ Σ = ] with filter Select the subsets that sum to the input
• infimum Get the smallest one

Answer 11

Retina 0.8.2, 30 bytes

.+
$*
(?=(\G1|11円)*1)11円?
$.&¶

Try it online! Link includes test cases. Explanation:

.+
$*

Convert to unary.

(?=(\G1|11円)*1)11円?

Repeatedly match the smallest number whose triangular number exceeds the remainder, calculated as one more than the largest number whose triangular number is strictly less than the input.

$.&¶

Convert to decimal and list each number on its own line.

Answer 12

Python 3.8 (pre-release), 45 bytes

Inspired by the answer of user tsh. -9 bytes thanks to user att.

lambda n:n*[p:=round((2*n)**.5)]and[p]+f(n-p)

Try it online!

Answer 13

Jelly, 7 bytes

ŒṗUQƑƇṂ

Try it online!

The only real difference from lyxal's Vyxal solution is that Jelly's integer partitions builtin generates them in nondecreasing order, requiring them to be reversed before finding the minimum.

ŒṗU Nonincreasing integer partitions.
 Ƈ Filter to those which
 Ƒ are unchanged by
 Q uniquification.
 Ṃ Take the minimum.

Answer 14

Charcoal, 21 bytes

NθWLΦθ‹Σ...·0κθ«≧−ιθ⟦Iι

Try it online! Link is to verbose version of code. Explanation:

Nθ

Input n.

WLΦθ‹Σ...·0κθ«

Count how many triangular numbers starting from 0 are less than n and repeat until this becomes zero.

≧−ιθ

Subtract that number from n.

⟦Iι

Output that number on its own line.