StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
primarykey
Id
3948113
data
AcceptedAnswerId
0
AnswerCount
0
ClosedDate
CommentCount
5
CommunityOwnedDate
CreationDate
2010-10-16T08:03:29.813
FavoriteCount
0
LastActivityDate
2010-10-17T10:53:06.087
LastEditDate
2010-10-17T10:53:06.087
LastEditorUserId
353410
OwnerUserId
353410
ParentId
3947937
PostTypeId
2
Score
30
ViewCount
0
LastEditorDisplayName
text
Body
<h1>Using RPN (reverse Polish Notation) </h1> For RPN intro see <a href="http://en.wikipedia.org/wiki/Reverse_Polish_notation" rel="noreferrer">here</a>. <h2>The Problem size</h2> We have to build a list of four numbers, which implies 3 operators. Those numbers and operators will be pushed or executed against a stack. Lets call the list of execution {a1 a2 a3 a4 a5 a6 a7}. {a1 a2} should be numbers, as there are no unary operations on the stack. {a7} should be an operator, to complete the operation. For {a3, a4, a5, a6} we have several options, but always at least two numbers must be in the stack to be able to operate. So the possible combinations are: (N= number, O=Operator) {N N O O}, {N O N O}, {O N O N}, {O N N O} and {N O O N}. The combination {O O N N} is forbidden because the stack is empty for the second O. So we have: <blockquote> <pre><code> | {N N O O} | | {N O N O} | {N N} | {O N O N} | {O} | {O N N O} | | {N O O N} | </code></pre> </blockquote> Now we will count the possible arrangements. Of course we are over counting because the commutative operator (Plus and Times) may cut the permutation tree in half, but the problem is small enough not to be bother by that. (We are also overcounting in those cases where the sequence is {O O}. but we simply go on ..) We have to choose 2 numbers in four for the first segment, that's 12 possible arrangements. For the middle segment, the two remaining numbers may only be permuted, that is a factor 2 But we have another factor 5 for counting the five alternatives for the middle segment. For the three operators, as they may repeat we have a factor 4^3=64 So the size of the problem is the product of the numbers in bold:12 2 5 64 = 7680. No optimization is needed, we may go ahead by brute force. The rest of the problem is to build the 7680 arrangements and the RPN evaluator. Both relatively easy tasks. I'll post it ...it's still a draft but here is too late! Will follow tomorrow! <h2>Edit: RPN Evaluator</h2> Here is the code for the recursive RPN evaluator. I choose to do it in a functional language (<a href="http://www.wolfram.com/" rel="noreferrer">Mathematica</a>) to simplify the operator parsing <pre><code>rpn[listipt_, stackipt_: {}] := Module[{list=listipt,stack=stackipt}, (*recursive rpn evaluator*) If[list == {}, Return[stack[[1]]]]; (*end*) If[NumberQ[list[[1]]], (*if numeric*) Return@rpn[Rest[list], PrependTo[stack,list[[1]]]]; (*push nbr and recurse*) , (stack[[2]]=list[[1]][stack[[2]], stack[[1]]]; (*if not, operate*) Return@rpn[Rest[list], Rest[stack]];); (*and recurse*) ]; ]; </code></pre> Usage examples <pre><code>rpn[{1, 1, 1, Plus, Plus}] 3 rpn[{2, 2, 2, Plus, Plus}] 6 rpn[{2, 3, 4, Plus, Times}] (* (4+3)*7 *) 14 rpn[{2, 3, 4, Plus, Divide}] (* (2+3)/4 *) 2/7 </code></pre> a bit later I'll post the tuples generator, show that they are 7680 and some funny results about the distribution of the possible results of the operations (in fact for the {1,2,3,4} set you can only get 230 different results!). <h2> Edit : Tuples construction </h2> First we explicitly construct the possibilities for the middle segment <pre><code>t1 = {{n3, n4, o1, o2}, {n3, o1, n4, o2}, {o1, n3, o2, n4}, {o1, n3, n4, o2}, {n3, o1, o2, n4}}; </code></pre> Now we prepend the two variations for {n1,n2} and the last operator <pre><code>t2 = Join[Map[Join[{n1, n2}, #, {o3}] &, t1], Map[Join[{n2, n1}, #, {o3}] &, t1]] ( bahh ... don't mind the code*) </code></pre> Resulting in our 10 different configurations <img src="https://i.stack.imgur.com/Qa1Me.png" alt="alt text"> Now we have to populate all those configurations with all the possible permutations of the numbers and operators. We first construct all number permutations as assignment rules for our tuples <pre><code> repListNumbers = (*construct all number permutations*) Table[{n1 -> #[[1]], n2 -> #[[2]], n3 -> #[[3]], n4 -> #[[4]]} &[i], {i, Permutations[{1, 2, 3, 4}]}]; </code></pre> These little beast have the form <pre><code> {n1 -> 1, n2 -> 2, n3 -> 3, n4 -> 4} </code></pre> And we can use them to replace vallues in our tuples. For example: <pre><code> {n1,n2,n3,o1,o2,n4,o3} /. {n1 -> 1, n2 -> 2, n3 -> 3, n4 -> 4} </code></pre> Results in <pre><code> {1,2,3,o1,o2,4,o3} </code></pre> Of course we may have constructed the replacement rules as a function to be able to change the number set at will. We do now something similar with the operators <pre><code>repListOps = (*Construct all possible 3 element tuples*) Table[{o1 -> #[[1]], o2 -> #[[2]], o3 -> #[[3]]} &[i], {i, Tuples[{Plus, Times, Divide, Subtract}, 3]}]; </code></pre> So we get a collection of things like <pre><code> {o1->Plus, o2->Plus, o3->Divide} </code></pre> Now we combine our tuples and all our replacement rules in one big list: <pre><code>t3 = Flatten[t2 /. repListNumbers /. repListOps, 2]; </code></pre> Which results in 15360 different calculations. But we know that there overcounted for a factor of two, so now we drop the repeated elements: <pre><code>t3 =Union[t3] </code></pre> And that give us our expected 7680 elements. There are still some overcounting, because {2,3,Times} = {3,2,Times} = 6, but that is ok for our current purpouses. <h2> Evaluating the results</h2> Now we have our RPN evaluator and all those tuples, and we want to know if a certain final result is possible. We simply have to ask if that number is contained in the set of results: <pre><code>In[252]:= MemberQ[rpn /@ t3, 24] Out[252]= True In[253]:= MemberQ[rpn /@ t3, 38] Out[253]= False </code></pre> In fact the bounds for the result set are: <pre><code>In[254]:= Max[rpn /@ t3] Out[254]= Max[36, ComplexInfinity] In[255]:= Min[rpn /@ t3] Out[255]= Min[-23, ComplexInfinity] </code></pre> The infinity results are due to the fact that I didn't care about divisions by zero, so they are there , just inside the set. The numeric interval is [-23,36]. If you want to know how many of the results are equal to 24, just count them <pre><code> In[259]:= Length@Select[t3, rpn[#] == 24 &] Out[259]= 484 </code></pre> Of course many of them are trivial permutations due to the commutative properties of "Plus" and "Times", but not all: <pre><code> {1, 2, Plus, 3, Plus, 4, Times} -> ((1+2)+3)*4 = 24 {2, 1, 4, 3, Times, Divide, Divide} -> 2/(1/(4*3)) = 24 </code></pre> There are none sequence using "Subtract" that gives 24! <pre><code> In[260]:= MemberQ[Flatten@Select[t3, rpn[#] == 24 &], Subtract] Out[260]= False </code></pre> <h2>Results Spectrum sample</h2> <img src="https://i.stack.imgur.com/aJ702.png" alt="alt text">
Tags
Title
singulars
PostAcceptedAnswerId
1. This table or related slice is empty.
PostParentId
1. POAlgorithm for permutations of operators and operands
 singulars
 PostTypePostTypeId
 PTQuestion
PostTypePostTypeId
1. PTAnswer
UserLastEditorUserId
1. USDr. belisarius
UserOwnerUserId
1. USDr. belisarius
plurals
PostLinksPostIdRelatedPostId
1. This table or related slice is empty.
PostLinksRelatedPostIdPostId
1. This table or related slice is empty.
PostsAcceptedAnswerId
1. POAlgorithm for permutations of operators and operands
 singulars
 PostTypePostTypeId
 PTQuestion
PostsParentIdCreationDate
1. This table or related slice is empty.
VotesPostIdCreationDate
1. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
2. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
3. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
CommentsPostId

Querying!

Guidance

A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.