 # operators and operands

Hi
I am asking my question. I think this problem is related to Dynamic programming concept.

Problem:
We have n operands and m operators. For example:
operands = {a,b,c,d}
operators = {*, -, +, /}

We must put operators between operands and create all of the possibility permutations.
F1 = a+b+c+d
F2 = a+b+c-d
F2 = a+b-c-d

Fi = a*b+c/d;

I could not implement the problem.
Is there anyone help me?

What is the value of max n and max m?

Is d+c+b+a valid permutation (I assume it’s not)?

I think that easiest to implement is DFS.

``````dfs( howManyYet, s )
if ( howManyYet == 1 )
print( ... ); // we have all info needed to print permutation
return;
for op in { '+', '-', '*', '/' }
dfs( howManyYet - 1, s + op );
``````

and initially you run `dfs( n, "" )`.

Instead of string you can use global char[], but it is only implementation detail.

1 Like

for op1 in ‘±/’:
for op2 in '±
/’:
for op3 in ‘±*/’:
print ‘a’ + op1 + ‘b’ + op2 + ‘c’ + op3 + ‘d’

4*4*4 = 64 possibilities. your compiler will possibly expand the loops himself… for higher values of n or m : http://www.kcats.org/csci/464/doc/knuth/fascicles/fasc2b.pdf

2 Likes

Thank you betlista!

1. The maximum length of operands is 4 (+,-,* and /), and maximum number of operations is 9. (almost 9 numbers).
2. Yes. d+c+b+a is not a valid permutation since we do not change the places.

I am trying using DFS as you mentioned and thank you again!
– amir

Hi Amir.
I’m from Iran like you! For solving this problem, you can do a brute force by 4 "for"s or a DFS as it’s described above.

(If you’re using Pascal, you can implement the solution with 4 "for"s so easy.)

Good luck. +1 for good link I’d like to see those 4 "for"s for n > 5.

This algorithm only works for n = 4.
If n is big, DFS will be the solution.

Is there any problem related to this concept on codechef?

3 Likes

Hello Erfan!
I am very happy to see you here.
There are many implementation for DFS Algorithm.
Would you please show me an efficient DFS source code for this problem.

Thank you again
– Amir

Do you have problem implement the idea from my answer (it is DFS)?

There are a samples of DFS implementation.