# Ordered sequence of ascending integer combinations

Write a program or function to produce the following output in the correct order.

EDIT: The symbols are not mathematical! The numbers just represent unique data and the + and - could be any two arbitrary symbols.

Take an non-negative integer input n. The first line is always -, even for n=0.

• If the current line is -, the next line is 1+2+ ... (n-1)+n-
• n=4: - => 1+2+3+4-
• If the last integer is equal to n, remove all integers from the end that are immediately followed by a -, then change the last + to a -
• n=4: 1-2+3-4- => 1-2-
• EDIT: When the string is full (all the integers from 1 to n are included), remove all integers from the end that are followed by a -, until you reach an integer followed by a +. Leave that integer but change its following + to a -
• Using the same example as immediately above (which does not follow -), remove 4-, remove 3-, change 2+ to 2-. 1- doesn't change since we stop at 2. Result: 1-2-
• If the last integer is less than n, append the remaining integers with a + after each one, except the final integer which should have a - appended
• n=4: 1+2- => 1+2-3+4-
• EDIT: If the current string is not full (does not contain all the integers from 1 to n), add each integer not already included in ascending order up to n-1 with a + after each one, and then append the last integer n followed by a -
• If the current line is 1-, append 2+, append 3+ which is n-1 if n=4. Then append 4-. Result: 1-2+3+4-
• If the current line contains all the integers and each one is immediately followed by a -, exit the code
• n=4: 1-2-3-4- => END

There must be no leading or trailing spaces on any line. There must be a line break between each line. There may or may not be a line break on the last line.

EDIT: You should test your code up to at least n=10 (over 1000 lines of output so I can't include it here). Any number that doesn't cause your code to run out of resources should (eventually!) produce the correct output but you don't have to wait for the universe to end!

This is , so shortest code in bytes wins!

Input n=0:

-


Input n=1:

-
1-


Input n=2:

-
1+2-
1-
1-2-


Input n=4:

-
1+2+3+4-
1+2+3-
1+2+3-4-
1+2-
1+2-3+4-
1+2-3-
1+2-3-4-
1-
1-2+3+4-
1-2+3-
1-2+3-4-
1-2-
1-2-3+4-
1-2-3-
1-2-3-4-


g takes an integer and returns a string.

g n=unlines$max"-".foldr(\(s,i)r->id=<<[show i++s:r|s:r>"+"])""<$>mapM(mapM(,)"+-")[1..n]


Try it online!

# How it works

• Loosely speaking, the algorithm constructs a list of all 2^n combinations 1+2+...n+, 1+2+...n- up to 1-2-...n-, strips away the final +-terminated numbers, and if the result is empty, replaces it with -.

• mapM(,)"+-" is a shorter way (using the function monad) to write \i->[('+',i),('-',i)].

• mapM(mapM(,)"+-")[1..n] generates (using the list monad for the outer mapM) a list with all combinations as lists of tuples e.g. [(1,'+'),(2,'-'),...,(n,'+')].
• foldr ... <$> ... combines each of these lists of tuples into a string, using the lambda expression to build it from the right. • (s,i) is a tuple of a sign and a number, and r is the string constructed from the tuples to its right. • id=<<[show i++s:r|s:r>"+"] prepends i and s to the string r constructed so far, but not if the sign s is positive and r is empty. • This is tested by comparing s:r to "+". By luck this is the lexicographically smallest string that can result from concatenating them, so the comparison can use > rather than /=. • Also by luck, "-" is smaller than any nonempty string that can be constructed by the fold, so the empty string can be replaced with it by using max. • Finally unlines turns the strings into a single string of lines. # Python 2, 101 bytes n=input() for i in range(2**n):s='';m=n;exec"s=m+'+-'[i%2]+s;s*='-'in s;i/=2;m-=1;"*m;print s or'-'  Try it online! • Nice use of s*=<condition> Commented Jul 14, 2017 at 4:00 # Python 2, 136141 133 bytes def f(n,s="+"): while"+"in s:s=s[:s.rfind("+")]+"-";print s[s>"-":];s+="+".join(map(str,range(len(s)/2+1,n+1)))+"-";print(n>0)*s[1:]  Try it online! The first - (un)surprisingly added a fair few bytes to the code. • So the string manipulation solution was shorter after all? Commented Jul 14, 2017 at 1:45 • Or I'm just bad :P Commented Jul 14, 2017 at 1:45 • The approach does seem to be shorter, but there are a few things that could be improved on yours; I'll post a comment with some tips in a bit. Commented Jul 14, 2017 at 1:47 • n=0 incorrectly produces two - lines. Commented Jul 14, 2017 at 2:20 • @CJDennis Fixed. Commented Jul 14, 2017 at 2:51 # Python 2, 150164159154146118 bytes115 112 bytes def f(n,i=0): while i<2**n:t=''.join(j+1+'+-'[i>>n+~j&1]for j in range(n));print t[:t.rfind('-')+1]or'-';i+=1  Try it online! Edit: Oops! It has to work for numbers greater than 4 as well... then chip away... until I realized I was overthinking it and saved 28 bytes... and then 6 more via little golfs. • Output is incorrect for input above n=4. Commented Jul 14, 2017 at 2:22 • @CJ Dennis I think it works now; output is the same as notjagan for,e.g, n=5 Commented Jul 14, 2017 at 2:38 • The output appears to be correct now! I'll add that you should test to at least 10... Commented Jul 14, 2017 at 2:46 • I just noticed that you set i=0 in the input! That means I can just generate lines from i onwards, such as f(24,16777200)! :-) Commented Jul 15, 2017 at 13:16 # Pyth, 23 bytes j+\-mssVSQd<Lx_d\-t^"+-  Demonstration The basis of this program is noticing that other than the initial -, the plus and minus sequence corresponds to the standard sequence of combinations of + and - with replacement, with all trailing + removed. Explanation: j+\-mssVSQd<Lx_d\-t^"+- j+\-mssVSQd<Lx_d\-t^"+-"Q Implicit string completion and variable introduction ^"+-"Q Form all sequences of + and - of length equal to the input, ordered lexicographically. t Remove the first one, which we don't use. <L Take the prefix of each one of length x index in _d the reversed string \- of '-'. m Map the results to sV Apply the sum function to pairs of SQ [1, 2, 3 ... input] d and the previous string s Sum the pairs. +\- Add a '-' on to the front of the list j Join on newlines.  # Python 2, 73 bytes f=lambda n,a=2,d='\n1':a<n+2and f(n,a+1,d+'+'+a)+d+f(n,a+1,d+-a)or'-'  Try it online! # Haskell, 70 bytes f n=unlines$"-":foldr(\i x->tail[show i++s:y|s<-"+-",y<-"":x])[][1..n]


Try it online!

# Python 3, 305 bytes

x=int(input())
o=lambda:list(range(1,x+1))or[0]
q=o()
q[-1]*=-1
print('-')
def f(a):print(''.join(str(abs(x))+'-+'[x>0]for x in a))
while any([k>0 for k in q])or[-k for k in q]!=o():
f(q)
if-q[-1]==x:
while q[-1]<0:q=q[:-1]
q[-1]*=-1
elif-q[-1]<x:
while q[-1]<x:q+=[abs(q[-1])+1]
q[-1]*=-1
f(q)


Try it online!

• I'm a bit confused by your tab/space mixing. First I didn't even think you COULD in Python 3, and second it seems to serve little purpose? Why bother doing <tab><space> when <space><space> would be the same # of bytes? I guess perhaps if you did the small indents with <space> and the larger with <tab> it would be saving a byte... Commented Jul 14, 2017 at 1:51
• @nmjcman101 erm. I must be really tired, or stupid, or both. I was trying to save bytes by doing that space/tab indent not tab/tabspace >< thanks! Commented Jul 14, 2017 at 1:55
• This is 17 bytes shorter, but it does exit on an error. Still trying to shorten that pesky q[-1] to q[0]. BTW: mixing tabs and spaces doesn't work in Python 3, so the current code yields an error. Commented Jul 14, 2017 at 1:58
• @notjagan oh hm. never mind then, it must have been because earlier I was being dumb :P but okay, thanks for the suggestion; i'll try to work from there Commented Jul 14, 2017 at 2:18