algorithm - how to generate all possible equations with a set of number and operators? -

i got maths , programming problem.

for given set of character {1,2,3,4,5,6,7,8,9,+,-,*,/}. , using set of characters randomly generate 10 (or let n) characters in array, i.e. [1,+,1,∗,3,5,7,8,1]. after need find possibility of equations using array of characters plus 1 character '='.

therefore in case, [1,+,1,∗,3,5,7,8,1] following equations: 1*1=1 , 3+5=8 , 7+1=8 , 15=8+7 , 15+3=18 (maybe more)

it can form multiple digit operation, i.e 15+3=18

so question trying using program generate equations all. guys give me ideas kind of algorithms can so? or methods it?

my current approach:

my approach not fast enough. idea is, minimum equation needs 3 number , 1 operator. and

1. i start randomly pick 4 members generated array. if these 4 members have 1 operator,
2. then add '='
3. form possible orders . e.g. 1,1,2,+ , have 112+=, 121+= ,1=12+ .... loop through that. ,
4. then increase 5 members , loop through it...
5. do until length of array generated

as mentioned in comments, appears np-complete, exponential, take really long, here's i'd nonetheless:

for each possible subset of input following:

generate permutations of a.

so each permutation corresponds equation (or thing that's equation doesn't have = sign).

now note there's going lot of invalid 'equation's. things 1**1. need ignore of these go. starting or ending operator or 2 operators in row invalid (or maybe not, 1*-2, -2+1 , 1--1 (?) valid (what 1++1 , +1+2?), anyway, i'm sure can figure out).

for each valid permutation, add number resulting evaluating set (well, (multi-)map of number equation).

do same permutations of remaining items when has been removed input (resulting in generated set).

now numbers appear in both sets valid equations. note (for lack of desire explain) you'll cross join-like process on equations have same number.

did generate each set twice, once on left, once on right? whoops. ok, here's fix: "pick element, each possible subset of input containing element...".

something think - separating out operators

advantage: may lot faster (not sure, may slower)
disadvantage: it's lot more complex

pre-process input, removing operators , have count each operator.

do same above, but, each permutation, generate permutations of operators can go. if done right, should able avoid invalid equations.

and have multiple sets put numbers (so you'll have 2 sets of sets), 1 each possible amount of each type of operators allowed, you'll compare against set (in other set of sets) such number of operators used.

to explain example:

input: [1,*,1,3,5,7,8,+,+,1]

input without operators: [1,1,3,5,7,8,1]

operators:

operator  count +         2 *         1 

an example subset: [1,7,8,1]
complement: [1,3,5]

now we'll have 2x 6 sets, 1 each combination of possible operators both sets:

            ++*      ++      +*      +      *      none subset      +1*1+78  11+7+8  1*1+78  117+8  1*178  1178 complement  +3*5+1   3+5+1   3*5+1   35+1   3*51   351 

the above examples, there lot more 1 equation going each set, need consider everywhere operators can go, example, considering ++*:

+1+1*78 +1+17*8 +11+7*8 1+1+7*8 1*1+7+8 1+1*7+8 etc. 

and considered permutation 1178 of example , 351 of complement, permutations need added (i.e. 1187, 1718, 1781, ... , 315, 513, 531, ...).

once of these added sets, match sets follows, use operators in equation:

subset      complement ++*    none ++     * +*     + +      +* *      ++ none   ++* 

to give better idea of happens, , assuming we're bad @ maths, can say: (taken above grid)

+1*1+78 = 351 11+7+8 = 3*51 1*1+78 = 35+1 etc. 

now you'll match equations using value evaluates (using sorted sets allow step through both @ same time in linear time). so, let's equation , b of subset both evaluate 79, , equation c , d of complement evaluate 79. you'll match them follows: (this meant cross join)

a = c = d b = c b = d 

and (if want these):

c = c = b d = d = b 

i hope clarifies it.