operators and operands

general
, , , ,
1

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?

2

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
3

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… :slight_smile:

for higher values of n or m : http://www.kcats.org/csci/464/doc/knuth/fascicles/fasc2b.pdf

2 Likes
4

Hi Amir.
I’m from Iran like you! :smiley:

I can help you about this problem.
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. :wink:

5

Is there any problem related to this concept on codechef?
Please give me link of that problem…

3 Likes
6

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

7

+1 for good link :wink:

8

I’d like to see those 4 "for"s for n > 5.

9

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

10

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

11

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

12

There are a samples of DFS implementation.
For ex: http://homepage.cs.uiowa.edu/~sriram/21/fall05/ExamplePrograms/ReaderFiles/Chap13/dfs/dfs.java

http://classes.soe.ucsc.edu/cmps201/Winter04/Project/Esc-karly/DFS.java

would you please tell me more about your answer:
dfs( howManyYet, s )