Re: hard recusive problem?


"Michael Press" <rubrum@xxxxxxxxxxx> wrote in message
news:rubrum-F8BBD7.22574423112007@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
In article
<UgI1j.24265$JD.3531@xxxxxxxxxxxxxxxxxxxxxxxxxx>,
"Jon Slaughter" <Jon_Slaughter@xxxxxxxxxxx> wrote:

This problem seems to be a little to hard for me(but probably not for you
guys)...

I'm trying to write a recursive algorithm that generates all the possible
combinations of adding and mulitplying elements from a finite set without
replacement

so if you have {a,b,c}

then a*b + c, a + b + c, b + c*a, a*(b + c), etc...

There is no distributive property because it would imply "replacement",
i.e., a*(b + c) = a*b + a*c and there are two a's. This doesn't mean a*(b
+
c) is invalid though as it is fine.

There communtivity and associativity though, a + b = b + c and a + b + c
= a
+ (b + c) = (a + b) + c = (a + c) + b. But these are not important. I
don't
mind if there is a distinction made here or not.

It seems that one can basically permute the set {a,b,c} and insert
allpossible combinations of operators inbetween but there is a little
issue
with the () grouping.

Maybe this can be done very easily with RPN(don't know to much about it
but
remember it being easy to deal with stuff like this)?

Anyone have any ideas or even know how to count all the possibilities?

Given a permutation of numbers, a,b,c, generating the
postfix expressions on binary operators is straightforward.
Start with depth := 0. Increase depth
with each argument pushed. Decrease depth with each
operator pushed, but only push an operator when depth >
1. Done when all arguments are used up and depth == 1.


This doesn't generate all(or any) permutations though because you are
starting with a fixed expression? You are converting an expression into a
stack?

How do you generate all possible valid RPN expressions directly? For
example, I created an RPN validator so I could just try all permutations of
the elements and keep only valid ones but this isn't very satisfactory.

Basically I need to go through all possible permutations but I need some
method of branching depending on if an element is an operator, an operand,
or by itself(this case may not be necessary as its obvious).

Of course is equivalent to just generating tree's so I guess I could
approach it from that perspective and it might be conceptually easier.

In that case I would just need to have the leafs to all be elements of the
set and the nodes to be operators. Changing a node though would influence
the whole tree pretty drastically. (for a single binary operator there is no
other possibility for a node so its not a big deal)

I think I might have an idea how to do it now... I'll try and code something
up and hopefully it will work ;) Its basically your idea but I didn't see
you mention anything about recursion which is required.

Generating the permutations of a multiset is harder. I
have not coded it. Suppose we have a multiset:
[A, A, ...A, B, B, ...B, ..., K, K, ...K]
where we hav a A's, b B's, ... k K's
Suppose a + b + ... + k = n
The number of pemutations is

n!
-------------
a! b! ... k!

With 5 permutations of arguments,
and four choices of operators in 4 places there are
5.4^4.14 expressions. The 14 is C_4, the fourth
Catalan number. C_n counts the number of balanced
strings of 2.n parentheses. Also the number of
complete binary trees on 2.n+1 vertices.


The Catalan numbers seems to be what I'm after for counting the number of
possibilities except they are for a single binary operator. I'll need to
somehow generalize it for multiple operators of arbitrary arity.

If you want to see a Perl code, email me.

I'll hold off for now. Lets see if I can do it. Although if you want maybe
you could write it and get some results for n = 1 through 10 and post them
so I can compare with what I get.

Thanks,
Jon


.

Relevant Pages

  • Re: Cubic
    ... They didn't let us touch Galois theory until my ... There are six permutations of the three roots; ... > permutations may be written in terms of the original coefficients AND the ... Just wanted to add with the actual explicit expressions: ...
    (sci.math)
  • Quantum Gravity 362.0: How Probable Causation/Influence (PI) Relates to S_4 in Section 361
    ... November 2008 (readers can look for their reference by name of author ... the "arrow" expressions with 4 ... Both the S_4 permutations and the PI expressions like are non- ... Every finite group is isomorphic with one or more groups of ...
    (sci.physics)
  • Algorithm For Calculating Permutations
    ... I would like to propose a recursive algorithm for calculating the ... A set with all the permutations of S. Each permutation is given ... Proof of Correctness. ... During the ith iteration of the for loop, ...
    (comp.theory)