Algorithm for permutations of operands and operators

[DouDou]

Hello,

I have been scratching my head over this for a while, but I can't seem to figure out the algorithm to find the right permutation(s) of operands and operators.

We basically have a list of 6 unsigned integers. Using arithmetic operations (addition, subtraction, multiplication, division), find the arithmetic expression that evaluates to a target integer.
Example:
myIntegers = {3, 7, 8, 10, 50, 100};
trgtInt = 315;

Solution is (50 + 10) * 7 - 100 - 8 + 3


We also have the following conditions:

1) Each number from the list can be used only once, but does not have to be used. i.e an expression with 5 or less numbers is accetable
2) Operators can be used multiple times

I am thinking a parenthesis-free notation like Polish or Reverse Polish notation should be used.

Any help would be much appreciated. Thanks!

[helios]

I am thinking a parenthesis-free notation like Polish or Reverse Polish notation should be used.

I tentatively agree. For example, for 4 operands, all the possible expression trees are
0 0 1 0 1 0 1
0 0 0 1 1 0 1
0 0 0 1 0 1 1
0 0 0 0 1 1 1
0 0 1 0 0 1 1
where 0 is an operand and 1 is an operator. I think it would work if you fix the first two operands and then permute the remaining 4 operands and 5 operators while ensuring that at any position, the number of operands to the left must be >= the number of operators + 1. For example, "0 0 1 1 1 1 1 0 0 0 0" would not generate a well-formed expression because the prefix "0 0 1 1 1" doesn't meet the previous requirement.

[Smac89]

The small amount of numbers (and operators) you are given to work with makes me think you are not expected to have a very efficient algorithm to accomplish this. So use the good ol' brute force and you should get your answer.

I will post a brute force solution later if you didn't come up with one

[DouDou]

Yes it appears that brute force might be the only way to do this. There are a couple things that one can do to save some time and eliminate some permutations. For example, since we are doing arithmetic operations, any expressions starting with a division where the modulo is different than zero can be skipped. So in the example I gave in my original post, an expression starting with "7 / 3 ..." can automatically be skipped.
I haven't really figured out a brute force solution. If you have, can you please post it. Many thanks!

[vaportrack]

I haven't really figured out a brute force solution.

hint....

for(A; ; ) {
for(B; ; ) {
if(B==A) continue;
for (C; ; ) {
if(C==B || C==A) continue;
for(D; ; ) {
if(D==B || D==A || D==C) continue;
for(E; ; ) {
//same
for (F; ; ) {
//bla bla bla
}}}}}}

There are other probably better ways but since this can be cached in the processor, its fast.
Dumping the results rather than just comparing for a fixed val will probably cause a cpu flush.
This thing doesn't do spaces well does it.

[Duthomhas]

Are you sure you can preempt divisions that are not modulo zero?

Are you expected to produce a solution? Or all solutions?

[Duthomhas]

I'd like an answer. This looks like an interesting problem. (And it is surely an algorithms class homework?)

The example you gave provides only one answer of many, but it does have the characteristic that it uses all the input numbers, which leads me to think that condition 1 is to be applied only if no solution using all numbers can be found. Is this correct?

A reasonable algorithm will produce all the solutions that use as few input numbers as possible first. (Assuming you want to avoid recalculating solutions.)


If you are still stuck, this is a permutations (for the input numbers) and combinations choose-k (for the operators) homework. The idea of using RPN is correct. For example, given four input numbers, you have exactly three possible RPN templates to play with:

    0 0 0 0 1 1 1
      0 0 0 1 1
        0 0 1

I even lined them up for you so you can see where the exploding rabbits come from if your algorithm doesn't try to pop out the fewer-operands solutions while it does the more-operands solutions. (Because you must calculate all possible solutions to the line below before you can find all the solutions to the line current. Consider the implications of this when you create your algorithm. And think of collapsible telescopes.)

Hope this helps.

[edit] At this point, try to get it working. Don't worry about optimizing away stuff like non-remainder divisions and the commutative property of addition and multiplication.

[Duthomhas]

Oops! It looks like I spoke without thinking. Looking at your first example solution, that cannot be calculated as an expression of the form ...0 0 0 0 1 1 1...
Sorry. Brute force, baby!

[DouDou]

I'd like an answer. This looks like an interesting problem. (And it is surely an algorithms class homework?)

This is actually for a game at my son's math club. I volunteered to develop a solver (I have made a cool userform already :)).

The example you gave provides only one answer of many, but it does have the characteristic that it uses all the input numbers, which leads me to think that condition 1 is to be applied only if no solution using all numbers can be found. Is this correct?

Not necessarily, the game rules are pretty simple. You have to come up with an arithmetic expression that evaluates to a target number. You can use all the integers in the list or a subset, but you can't use the same number more than one time.

I am still scratching my head. Hopefully I will come up with a solution before Tuesday :)

[helios]

It's not as difficult as it seems. Here are all the possible solutions for your example (using integer /): http://pastebin.com/P9zSjgeN

[DouDou]

It's not as difficult as it seems. Here are all the possible solutions for your example (using integer /): http://pastebin.com/P9zSjgeN

Cool! I don't see the code though. Can you please post it?

[helios]

I wouldn't want to spoil your fun.

[Duthomhas]

That's far too many solutions.

(I won't take the time to examine them all, but number 16, for example, produces a negative 315, which is not an answer to the problem.)


In any case, helios's solutions brings up an important issue when calculating results: how do we handle intermediary values?

I posit three options:

- Permit only exact division: quotient must be an integer
  This behavior is what OP desires (as per his second post above)
  (157 solutions to OP's example)

- Allow floating point intermediaries when dividing
  An example is 7 = 1 + 4 / (2 / 3).
  (232 solutions to OP's example)

- Use "integer division" (discard any remainder)
  (558 solutions to OP's example)

This is actually for a game at my son's math club.

This is a pretty brutal problem for your average child, as it is NP-complete and requires both permutations and combinations, not to mention generating valid RPN sequences and nested loops.

And it is pretty slow.

There are some things you can do to shave time (like shaving recalculating subsolutions), but you cannot shave testing every solution.

I've only got a brute-force algorithm in Tcl ATM. The strict division problem works in about 3 minutes. I'm sure I can cut a lot of that out by getting rid of shimmering and using some prefix trees and caching output. (And by writing it in C++.)

If you only need a single solution, you can usually get that pretty quick though, and just quit after it is found. If you want to check a user's solution that requires only evaluating the expression itself, which is faster than anything else.


Caveats: my solution may have missed something!
(I don't think it did, but I still have to carefully validate my RPN sequence generator.)

[helios]

That's far too many solutions.

Notice that I treat x+y and y+x as different solutions. I don't think there are any duplicates, otherwise.

number 16, for example, produces a negative 315

You made a mistake when converting to infix notation.
50 8 3 - - 7 * => (50 - (8 - 3)) * 7

A fifth option for division would be that quotients may be rational, but they will be compared to an integer at the end of the evaluation.

EDIT: If you want to check your RPN generator, this is what mine generates for 6 operands:

0 0 0 0 0 0 1 1 1 1 1
0 0 0 0 0 1 0 1 1 1 1
0 0 0 0 0 1 1 0 1 1 1
0 0 0 0 0 1 1 1 0 1 1
0 0 0 0 0 1 1 1 1 0 1
0 0 0 0 1 0 0 1 1 1 1
0 0 0 0 1 0 1 0 1 1 1
0 0 0 0 1 0 1 1 0 1 1
0 0 0 0 1 0 1 1 1 0 1
0 0 0 0 1 1 0 0 1 1 1
0 0 0 0 1 1 0 1 0 1 1
0 0 0 0 1 1 0 1 1 0 1
0 0 0 0 1 1 1 0 0 1 1
0 0 0 0 1 1 1 0 1 0 1
0 0 0 1 0 0 0 1 1 1 1
0 0 0 1 0 0 1 0 1 1 1
0 0 0 1 0 0 1 1 0 1 1
0 0 0 1 0 0 1 1 1 0 1
0 0 0 1 0 1 0 0 1 1 1
0 0 0 1 0 1 0 1 0 1 1
0 0 0 1 0 1 0 1 1 0 1
0 0 0 1 0 1 1 0 0 1 1
0 0 0 1 0 1 1 0 1 0 1
0 0 0 1 1 0 0 0 1 1 1
0 0 0 1 1 0 0 1 0 1 1
0 0 0 1 1 0 0 1 1 0 1
0 0 0 1 1 0 1 0 0 1 1
0 0 0 1 1 0 1 0 1 0 1
0 0 1 0 0 0 0 1 1 1 1
0 0 1 0 0 0 1 0 1 1 1
0 0 1 0 0 0 1 1 0 1 1
0 0 1 0 0 0 1 1 1 0 1
0 0 1 0 0 1 0 0 1 1 1
0 0 1 0 0 1 0 1 0 1 1
0 0 1 0 0 1 0 1 1 0 1
0 0 1 0 0 1 1 0 0 1 1
0 0 1 0 0 1 1 0 1 0 1
0 0 1 0 1 0 0 0 1 1 1
0 0 1 0 1 0 0 1 0 1 1
0 0 1 0 1 0 0 1 1 0 1
0 0 1 0 1 0 1 0 0 1 1
0 0 1 0 1 0 1 0 1 0 1

I start from 00000011111 and then I permute 00[000011111]. Validation is simple:

bool is_valid_rpn_form(const std::vector<bool> &s){
	int n = 0;
	for (const auto &c : s){
		if (!c)
			n++;
		else
			n--;
		if (n < 1)
			return 0;
	}
	return n == 1;
}

[DouDou]

Okay this is what I have come up with far.

#include <string>
int main()
{
	
	std::string strings[26] = { "3", "7", "8", "10", "50", "100", "+", "+", "+", "+", "+", "-", "-", "-", "-", "-", "*", "*", "*", "*", "*", "/", "/", "/", "/", "/"};
	int target = 315;
	for (short i1 = 0; i1 <= 5; ++i1) // First character must always be a operand
	{
		for (short i2 = 0; i2 <= 5; ++i2) // Second character must always be an operand
		{
			for (short i3 = 0; i3 <= 25; ++i3)
			{
				/*Starting at third level and for every odd level,

				check if strings[i1] + strings[i2] + strings[i3] is a valid RPN
				If true then evaluate expression using an RPN parser,
				if value = target then print to file
				*/
				for (short i4 = 0; i4 <= 25; ++i4)
				{
					for (short i5 = 0; i5 <= 25; ++i5)
					{
						// check here
						for (short i6 = 0; i6 <= 25; ++i6)
						{
							for (short i7 = 0; i7 <= 25; ++i7)
							{
								//check here
								for (short i8 = 0; i8 <= 25; ++i8)
								{
									for (short i9 = 0; i9 <= 25; ++i9)
									{
										//check here
										for (short i10 = 0; i10 <= 25; ++i10)
										{
											for (short i11 = 6; i11 <= 25; ++i11) // last character (11th) must always be an operator
											{
												//check here
											}
										}
									}
								}
							}
						}
					}
				}
			}
		}
	}
	system("PAUSE");
}

Perhaps not the most elegant but it may work.

[Duthomhas]

I swear my brain is addled.

[Smac89]

Finally solved it, but the output it produced for 315 was so long that I could not post it here, due to printing duplicates. But here is the source code and small output using less numbers:


Hope you guys don't mind Java
http://ideone.com/pyTnfv

A snippet of what 315 produced with the values supplied by OP:

((8 + 100 + 50 + 10) / 3 + 7) * 5
(8 + 100 - 50 + 3) * 5 + 10
(8 + 100 - 50 - 3 - 10) * 7
(8 + 100 - 50 + 7) * 5 - 10
(8 + 100 - 50 - 10 - 3) * 7
(((8 + 100) / 50 + 7) * 10 + 3) * 5
((8 - 100) / 3 + 7) * 50 + 5 + 10
(7 + 100 + 8 - 50) * 5 - 10
((7 + 100 - 8) * 10 + 5 - 50) / 3
((7 + 100 - 8) * 10 - 50 + 5) / 3
(7 + 100 - 10 + 8) * 3
((7 + 100 + 50) * 10 - 3 + 8) / 5
((7 + 100 + 50) * 10 + 8 - 3) / 5
100 / 5 * 50 * 3 / 10 + 7 + 8
100 / 5 * 50 * 3 / 10 + 8 + 7
(100 / 5 * 50 / 8 + 10) / 3 * 7
(100 / 5 * 50 / 8 + 10) * 7 / 3
(100 / 5 * 50 - 10) / 3 - 7 - 8
(100 / 5 * 50 - 10) / 3 - 8 - 7
100 / 5 * 50 / 10 * 3 + 7 + 8
(50 + 10) * 7 - 100 - 5
(50 + 10) * 7 - 100 - 8 + 3
((50 + 10 + 8 + 100) / 3 + 7) * 5
((50 + 10 - 8) * 3 + 7 - 100) * 5
((50 + 10 - 8) * 3 - 100 + 7) * 5
((50 + 10) * 8 * 3 + 100) / 5 + 7

And there is brute force for you :)

EDIT: I had an extra value (5) in the list of values that I never noticed

[helios]

Huh. You got it pretty short. What's the run time for OP's example?

[Smac89]

Had a little bit of trouble setting up the timer, but here it is:

Starting timer!
-------------------------

Finshed in 203 milliseconds!
-------------------------

architecture - Windows 8 intel core i5-4200M @2.5GHz

The above is done without printing the output

[helios]

Wot? My 3770 needs ~1.5 s to find all the solutions. Are you sure you covered the entire search space? It should take around 33.5 M iterations, unless you're doing some very smart culling.