# Challenge

Given a positive integer $$\N \ge 3\$$, generate an alternating series of $$\N\$$ random numbers within the range $$\[1, N]\$$, such that their sum equals $$\N\$$. Expressed mathematically as

$$N = \sum_{i=1}^{N} (-1)^{i-1} a_i$$ where $$\a_i \in [1,N]\$$ are random terms.

Input

$$\N\$$

Output

A string representing the alternating series of $$\N\$$ terms (each prefixed by $$\+\$$ or $$\-\$$) that sum up to $$\N\$$.

Notes

Random numbers can be generated using any standard random number generation function. For example, rand() in C, random.randint() in Python, Math.random() in Javascript, etc.,...

# Examples

N alternating series
3 +1-1+3
4 +4-1+3-2
5 +4-2+4-4+3
6 +5-1+4-4+3-1
7 +6-1+4-7+4-1+2
8 +6-7+7-5+7-1+2-1
9 +3-7+8-3+2-8+9-2+7
10 +10-4+4-2+8-3+1-4+5-5
11 +11-7+1-2+2-10+3-5+10-2+10
... ...
• "Alternating" needs to be better defined within the spec here. Feb 5 at 1:18
• Do the outputs have to be equally likely?
– xnor
Feb 5 at 2:11
• Saying you should produce one or several outputs randomly without further specification is one of the things to avoid when writing challenges, and IMO just saying that you have to use a uniform RNG with values in $[1,N]$ isn't enough - do you have to use the straightforward rejection sampling algorithm? Feb 5 at 9:15
• To solve the issue mentioned by xnor and Command Master, a simple solution could be requiring each possible output to have nonzero probability Feb 5 at 12:44
• @vengy choosing each term uniformly and testing for correctness repeatedly will be biased towards some answers over others (although all valid solutions are still possible outputs). Feb 5 at 17:36

# Jelly, 15 bytes

ṗḅ-⁼ɗƇ⁸XṚṭNƭ€”+


A full program that accepts a positive integer, $$\n\$$, and prints a possible alternating sum, in the given format, with $$\n\$$ terms with absolute values from $$\[1,N]\$$.

All possible outputs are equally likely.

Try it online!

### How?

ṗḅ-⁼ɗƇ⁸XṚṭNƭ€”+ - Main Link: positive integer, n
ṗ               - {[1..n]} Cartisian power {n}
-> all length n lists formed of values [1..n]
Ƈ          - keep those for which:
ɗ ⁸         -   last three links as a dyad - f(potential, n)
-             -     literal -1
ḅ              -     convert {potential} from base -1
-> last - penultimate + antepenultimate - ...
⁼            -     equals {n}?
X        - uniform choice
Ṛ       - reverse
€   - for each:
ƭ    -   alternate between:
ṭ   ”+ -     a) tack to '+'; and
N     -     b) negate
- implicit, smashing print

• $[3,6]$ run quicky, but $7$ onwards are really slow. Is that a result of the language? Thanks. Feb 5 at 18:05
• That is mostly a result of the implementation, it is first getting all $n^n$ possible arrays of $n$ numbers from the alphabet $[1,n]$. This is golf :) Feb 5 at 18:19

Assuming $$\n\$$ is in $$\A1\$$

=LET(F,LAMBDA(F,LET(o,JOIN(,MAKEARRAY(A1,1,LAMBDA(i,_,IF(MOD(i,2),"+","-")&RANDBETWEEN(1,A1)))),IF(A1=SORTN(QUERY(,"select "&MID(o,2,99))),o,F(F)))),F(F))


Recursive formula that generates a random sequence. If the sum is $$\n\$$, it returns it, otherwise it generates a new sequence and the process is repeated.

• Looks like it works most of the time for the range [3,35], but higher values give an error. Feb 5 at 3:46
• I believe changing 99 to LEN(o) should fix the logic of the formula and maybe the error too. But performance-wise it's still going to be pretty bad.
– z..
Feb 5 at 5:03

# Python 3.8 (pre-release), 120 bytes

from random import*
def f(n):
while sum(L:=[s*randint(1,n)for s in(1,-1)*n][:n])-n:1
return''.join('%+d'%v for v in L)


Try it online!

Brute-force method. Generates a list of $$\N\$$ random numbers until their sum is equal to $$\N\$$.

# 05AB1E, 19 bytes

L¤ãε(2Å€Ä'+ì]ʒOQ}ΩJ


ε(2Å€Ä'+ì] could alternatively be ε'+ìι(.ι} for the same byte-count:

Explanation:

L             # Push a list in the range [1, (implicit) input]
¤            # Push its last item (without popping): the input
ã           # Cartesian product to have all possible input-sized lists
ε          # Map over each inner list:
(         #  Negate all values
2Å€      #  Then for every 2nd item (0-based index is divisible by 2):
Ä     #   Absolute value to make the negative value positive again
'+ì '#   Prepend a "+" instead
]          # Close both the every and outer maps
ʒ         # Filter:
O        #  Sum the values in the list together
Q       #  Check whether this is equal to the (implicit) input-integer
}Ω        # After the filter: keep a random inner list
J       # Join it together to a single string
# (which is output implicitly as result)

ε          # Map over each inner list:
'+ì      '#  Prepend a "+" before each value
ι      #  Uninterleave the list into two parts
#  Pop and push both parts separately to the stack
(    #  Negate the values in the top list
.ι  #  Interleave the two lists back together
}          # Close the map


# Charcoal, 25 bytes

ＮθＷ⁻↨⮌υ±¹θ≔Ｅθ⊕‽θυ⭆υ⁺§+-κι


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

Ｎθ


Input N.

Ｗ⁻↨⮌υ±¹θ


Until interpreting the reverse of the predefined empty list as base -1 results in N, ...

≔Ｅθ⊕‽θυ


... assign N random integers in the range 1..N to the list.

⭆υ⁺§+-κι


Output the list with + and - signs inserted as appropriate.

# Pyth, 20 bytes

s+V*"+-"QOf!u-HGTQ^S


Try it online!

### Explanation

s+V*"+-"QOf!u-HGTQ^SQQ    # Implicitly add QQ
# Implicitly assign Q = eval(input())
SQ     # range(1, Q+1)
^  Q    # repeated cartesian product, Q times
f               # filter over lambda T
u-HGTQ        #   reduce T over subtraction with Q as the starting value
!              #   true if 0
O                # choose a random value from the list
*"+-"Q                 # "+-" repeated Q times
s                         # join into one string


# JavaScript (ES6), 74 bytes

f=(n,i,s)=>i^n?f(n,-~i,[s]+"+-"[i&1]+-~(Math.random()*n)):eval(s)-n?f(n):s


Try it online!

### Commented

f = (               // f is a recursive function taking:
n,                //   n = input
i,                //   i = counter, initially undefined
s                 //   s = output string, initially undefined
) =>                //
i ^ n ?             // if i is not equal to n:
f(                //   do a recursive call:
n,              //     pass n unchanged
-~i,            //     increment the counter
[s] +           //     append to s ...
"+-"[i & 1] +   //     ... either "+" or "-" according to
//     the parity of i
-~(             //
Math.random() //     followed by a random integer
* n           //     in [1, n]
)               //
)                 //   end of recursive call
:                   // else:
eval(s)           //   evaluate the expression
- n ?             //   if the result is not equal to n:
f(n)            //     try again
:                 //   else:
s               //     stop and return it


# C (gcc), 118 112 bytes

-6 bytes, thanks to @Arnauld

i=0,s=0,a[];f(n){for(s=0;s-n;)for(i=s=0;i<n;)s+=a[i++]=(i%2*2-1)*~(rand()%n);for(i=0;i<n;)printf("%+d",a[i++]);}


Try in online!

• 108 bytes Feb 7 at 4:43