artist has asked for the wisdom of the Perl Monks concerning the following question:
I am trying to solve a permutation probelm and looking for pointers. The different permutation we can create by putting pair of paranthesis before,after or in between given number.
Example: for p=2 and n= 123, we may have:
(1) (2) 3 (1) 2 (3) (1 2) (3) (1 (2 3)) ((1 2 3)) 1 ((2 3))etc..
Thanks,
artist
|
---|
Replies are listed 'Best First'. | |
---|---|
(jeffa) Re: Parens permutations
by jeffa (Bishop) on Aug 02, 2003 at 23:28 UTC | |
jeffa L-LL-L--L-LL-L--L-LL-L-- -R--R-RR-R--R-RR-R--R-RR B--B--B--B--B--B--B--B-- H---H---H---H---H---H--- (the triplet paradiddle with high-hat) | [reply] [d/l] |
Re: Parens permutations
by dws (Chancellor) on Aug 02, 2003 at 23:51 UTC | |
| [reply] [d/l] [select] |
by artist (Parson) on Aug 03, 2003 at 01:16 UTC | |
The number of parens are given. So if p = 2 then 1 ((2 3)) => valid ((1 2 3)) => valid 1 (((2 3))) => invalid | [reply] |
Re: Parens permutations
by barrachois (Pilgrim) on Aug 03, 2003 at 21:53 UTC | |
In what context did this problem come about? - barrachois
| [reply] [d/l] |
Re: Parens permutations (order)
by tye (Sage) on Aug 05, 2003 at 17:02 UTC | |
Well, I was just about to finish previewing my idea when I realized that it didn't find arrangements of parens like (()()). Which lead me to a simpler solution anyway. In any case, the trick is to come up with a order for the solutions so that you can find the solutions in that order and then you don't have to worry about checking for duplicates. This is important because finding duplicates requires you be able to compare a new result to all previous results but the number of results for this type of problem quickly becomes so huge that such a comparison becomes infeasible. For this problem, I think we need to order first either based on the position of the open parens, or based on the position of the closed parens. So, for a final arrangement like (1((2)3))(4), we can build up the parens either like (123)4 -> (1(23))4 -> (1((2)3)4 -> (1((2)3))(4) or like 1(2)34 -> 1((2)3)4 -> (1((2)3))4 -> (1((2)3))(4). Let's go with the first case. So, start by building a loop or iterator (we won't have enough memory if we start computing whole lists of solutions along the way) that adds one set of parens: (1)234, (12)34, (123)4, (1234), 1(2)34, 1(23)4, 1(234), 12(3)4, 12(34), and 123(4). Then improve this so that it knows to add the next set of parens such that 1) nesting is not violated and 2) the opening paren is inserted *after* all of the existing opening parens. Then apply this solution N times to get N sets of parens. So, if you have 1(23)4, adding the next set of parens would proceed like so: 1((2)3)4, 1((23))4, 1(2(3))4, 1(23)(4). That is, start with the opening paren in the first possible location (right after the last opening paren already present) and progress this position forward one step at a time. For each position of the opening paren, step the position of the closing paren along, starting right after the digit after the new open paren, and continuing until the end of the continguous string of digits (after which we'd either hit end of string or violate nesting of parens). This very last part almost screams "regex", and with experimental features you could even get the regex engine to find all of these for you as it back-tracks matching \d+? over and over. But such wouldn't give us an iterator (and I don't like using experimental features), so... Read more... (3 kB) Which can give you all of the results: Or just a table of counts: - tye | [reply] [d/l] [select] |
by tye (Sage) on Aug 05, 2003 at 19:57 UTC | |
And these counts can be computed much faster using: Taking $len==4 for example, that boils down to: which is an interesting equation. A mathematician might write it as: And it is interesting to me that I need to test for 1==$len but I don't need to test for 0==$parens. Note that replacing $len with $parens+1 and $parens with $len-1 gives us the same values. So I suspect the equation can be rewritten as (mostly) the product of two binomial coefficents (number of different subsets of size S you can pick from a set of size N). But I don't have the time to figure out all of the off-by-ones at the moment. Update: But C(P+L,P+1) == C(P+L,L-1) == (P+L)!/(P+1)!/(L-1)! so ?? == C(P+L,P+1)/(P+L). So the number of ways to put P parens into a string of length L is ...I think. (: Now, someone just needs to explain why this formula makes sense. Then we'll have worked the problem "backward" and in future math classes the solution can be presented in the "forward" direction and we can intimidate another generation of students into thinking that they'd never be able to solve math problems... thus continuing a long tradition of mathematicians. ;) - tye | [reply] [d/l] [select] |
by artist (Parson) on Aug 05, 2003 at 20:25 UTC | |
I had suspected the factorials once I saw symmetry and little similarity with pascal's triangle, but tye came out faster even with the solution. | [reply] |
by gamzeozl (Initiate) on Jan 22, 2008 at 07:41 UTC | |
| [reply] |
Re: Parens permutations
by Limbic~Region (Chancellor) on Aug 05, 2003 at 05:44 UTC | |
Please forgive me as I am incredibly tired, but I originally told you in the CB this sounded like a math problem. Unfortunately I do not believe it is a simple algebraic formula. Lets change n=123 to n=3 since you are talking about a 3 digit number. Now we have a few problems.
Problem number 1: The equation to determine the number of permutations seems to change with p.
p = 2
Second problem: There can be some ambiguity in what we are actually grouping: Can be seen as either 1 & 3 + 2 or 1 & 2 + 2 & 3. This breaks the formula for p = 2 since: is not correct as barrachois pointed out - it is actually 20 since two permutations, while different, look the same. I didn't bother going any further than this to see if the simple formulas for different values of p could be generalized. Sorry - L~R | [reply] [d/l] [select] |
Re: Parens permutations
by graff (Chancellor) on Aug 05, 2003 at 04:56 UTC | |
Given: You have m + 1 positions around the array elements, such that: There would be a number of ways to build a nested loop to iterate through the enumeration of the set -- e.g. start with all open parens at position 0 and all close parens at position 1, move the close parens across the remaining positions in the inner loop, and move the open parens in the outer loop, or something to that effect. I expect there would also be some clever formula to compute the size of the set, given just the values of m and p, without having to enumerate. That's how I would proceed if I needed to do this (but I don't feel like I need to just now...) update: I guess this is rather close to the solution that barrachois proposed above. I forgot to mention that, when printing the enumeration, the following condition is also needed: when a medial position contains both open and close parens, simply print all the close parens first, then all the open parens, for that position. This, along with some logic to do the correct initial placement of close parens for each possible placement of open parens, will ensure that the output set is well formed (barrachois' recursive descent of the structure to check proper nesting would not be needed). | [reply] |