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
cyberax
November 29, 2012, 11:57pm
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…
for higher values of n or m : http://www.kcats.org/csci/464/doc/knuth/fascicles/fasc2b.pdf
2 Likes
Thank you betlista!
The maximum length of operands is 4 (+,-,* and /), and maximum number of operations is 9. (almost 9 numbers).
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!
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.
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?
Please give me link of that problem…
2 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)?