Parens permutations

artist has asked for the wisdom of the Perl Monks concerning the following question:

Dear Monks
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

Comment on Parens permutations

Replies are listed 'Best First'.
(jeffa) Re: Parens permutations by jeffa (Bishop) on Aug 02, 2003 at 23:28 UTC
Interesting problem ... this is as far as i got before giving up. I borrowed some of merlyn's code from Permutations and combinations: `for my $row (combinations(1..3)) { my @row = 1..3; $row[$_-1] = "($row[$_-1])" for @$row; print "@row\n"; } # from [id://24270] by [merlyn] sub combinations { return [] unless @_; my $first = shift; my @rest = combinations(@_); return @rest, map { [$first, @$_] } @rest; } __END__ 1 2 3 1 2 (3) 1 (2) 3 1 (2) (3) (1) 2 3 (1) 2 (3) (1) (2) 3 (1) (2) (3)` [download] 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
If `1 ((2 3))` is valid, then what about `1 (((2 3))) ?` If that's valid, then you have a countably infinite number of possible permutations. I kinda doubt the problem is phrased to allow that. Update: D'oh. So that's what p= means.	[reply] [d/l] [select]
Re: Re: Parens permutations by artist (Parson) on Aug 03, 2003 at 01:16 UTC
Hi dws, The number of parens are given. So if p = 2 then 1 ((2 3)) => valid ((1 2 3)) => valid 1 (((2 3))) => invalid artist	[reply]
Re: Parens permutations by barrachois (Pilgrim) on Aug 03, 2003 at 21:53 UTC
I didn't make much progress on an analytic solution, but here's some code to traverse the permutations by brute force, and some thinking out loud. Kinda fun. In what context did this problem come about? - barrachois #!/usr/bin/perl -w use strict; # Dear Monks # # 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 # # -------------------------------------------------------- # # Given n=3, p=2 as above, without parens we have n+1=4 # places where parens can be placed, i.e. on the dots in # # . 1 . 2 . 3 . # # Assuming that arrangements like "() 1 2 3" are illegal, # a left-paren may be placed at a dot numbered # L=0..(n-1) and its corresponding right-paren at R=(L+1)..n # # Therefore the number of ways I can place a single pair # of parens around n digits is # # 3 (1) 2 3 , (1 2) 3 , (1 2 3) L=0; R=1,2,3 # + 2 1 (2) 3 , 1 (2 3) L=1; R=2,3 # + 1 1 2 (3) L=2; R=3 # --- # total 6 = (n)(n+1)/2 # # Now let's try to place another pair of parens. # These can be put at the same dot locations; # the trick will be to avoid counting arrangements like # "(1)(2)3" twice. For visual clarity, I'll use # sqaure brackets for the second parens, working # forward from the six single paren patterns above. # # For the first pattern "(1) 2 3", adding a second # pair of brackets again gives six possibilities. # # [(1)] 2 3 , [(1) 2] 3 , [(1) 2 3] 6 new # (1) [2] 3 , (1) [2 3] # (1) 2 [3] # # However, trying the same approach to the second # pattern "(1 2) 3" starts to give arrangments that # have already been found. (Remember that the [] # and () symbols are actually identical and interchangeable.) # # Try all six combinations starting from the next # single pattern "(1 2) 3" gives # ([1] 2) 3 OLD, ([1 2]) 3 NEW, [(1 2) 3] NEW +5 new # (1 [2]) 3 NEW, (1 [2) 3] NEW, # (1 2) [3] NEW # of which the first is a repeat of "[(1) 2] 3" and # the rest are new. # # Continuing in the same vein gives # # ([1] 2 3) OLD, ([1 2] 3) OLD, [(1 2 3)] NEW +3 new # (1 [2] 3) OLD, (1 [2 3]) NEW, # (1 2 [3]) NEW # # Hmmm. I stared at this but haven't really found an obvious pattern. # # But whether there is or not, feels like its time # to write some code. If I loop over all the possible # positions of the left and right parens, as I'm doing above, # I can just remember which ones I've found already in # a hash, and keep the new ones. # # This may not be the most efficient, but it'll get the job done. # # Here's what the output look like : # # Looking for permutations of 2 pairs of parens around 3 digits. # ((1))23 # ((1)2)3 # ((1)23) # (1)(2)3 # (1)(23) # (1)2(3) # ((12))3 # ((12)3) # (1(2))3 # (1(2)3) # (12)(3) # ((123)) # (1(23)) # (12(3)) # 1((2))3 # 1((2)3) # 1(2)(3) # 1((23)) # 1(2(3)) # 12((3)) # Total number of permutations = 20 my $n; # number of digits my $p; # number of paren pairs my @leftparens; # count of left parens at each position my @rightparens; # count of right parens at each position my %seen; # permutations generated my $DEBUG = 0; init(3,2); # define n,p print " Looking for permutations of $p pairs of parens around $n digit +s. \n"; addParenPair(1); # add first pair of parens, and others recursively print " Total number of permutations = " . scalar(keys %seen) . "\n"; # ------------------------------------------------------------ sub init { ($n, $p) = @_; @leftparens = (0)x($n+1); @rightparens = (0)x($n+1); %seen = (); } # Convert current permutation as recorded in @leftparens and @rightpar +ens to a string. sub permutationAsString { my $result = "("x$leftparens[0]; for my $digit (1..$n){ $result .= $digit . ")"x$rightparens[$digit] . "("x$leftparens[$di +git]; } return $result; } # If we haven't seen this one, remember it and print it out. sub analyzePermutation { my $permutation = permutationAsString(); unless ($seen{$permutation}){ $seen{$permutation}++; print " " . $permutation . "\n"; } } # Recursive descent routine to put in next pair of parens # and analyze the result if all the parens have been placed. # If $DEBUG is true, it'll also print some progress reports. sub addParenPair { my ($whichPair) = @_; for my $left (0..($n-1)){ $leftparens[$left]++; for my $right (($left+1)..$n){ $rightparens[$right]++; if ($whichPair == $p){ analyzePermutation(); } else { if ($DEBUG){ print " "x$whichPair . "Permutation so far is " . permutationAsString() . "; adding pair " . ($whichPair+1) +. "\n"; } my $lastCount = scalar(keys %seen); addParenPair($whichPair+1); my $newPerms = scalar(keys %seen) - $lastCount; if ($DEBUG){ print " "x$whichPair . "new permutations added = $newPerms. + \n"; } } $rightparens[$right]--; } $leftparens[$left]--; } } [download]	[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: `> parenperms 3 12 1: (((1)))2 2: ((1))(2) 3: (1)((2)) 4: (((1))2) 5: ((1)(2)) 6: (((1)2)) 7: (((12))) 8: ((1(2))) 9: (1((2))) 10: 1(((2)))` [download] Or just a table of counts: `> parenperms 1..7 1..7 parens lengths 1 2 3 4 5 6 7 1: 1 3 6 10 15 21 28 2: 1 6 20 50 105 196 336 3: 1 10 50 175 490 1176 2520 4: 1 15 105 490 1764 5292 13860 5: 1 21 196 1176 5292 19404 60984 6: 1 28 336 2520 13860 60984 226512 7: 1 36 540 4950 32670 169884 736164` [download] - tye	[reply] [d/l] [select]
Re^2: Parens permutations (formula) by tye (Sage) on Aug 05, 2003 at 19:57 UTC
And these counts can be computed much faster using: `sub Prod { my( $i, $j )= @_; my $f= $i; $f = $j if $i < $j; for my $p ( $i+1..$j-1 ) { $f = $p$p; } return $f; } sub Count { my( $parens, $len )= @_; return 1 if 1 == $len; return Prod($parens+1,$parens+$len)/Prod(1,$len) }` [download] Taking $len==4 for example, that boils down to: `(P+1)(P+2)^2(P+3)^2(P+4)/1/2^2/3^2/4` [download] which is an interesting equation. A mathematician might write it as: `(P+L)!/P!(P+L)!/P!L/(P+1)/(P+L)/L!/L! or [(P+L)!/P!/L!]^21L/(P+1)/(P+L)` [download] 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: `[(P+L)!/P!/L!]^21L/(P+1)/(P+L) == [ C(P+L,P) ] * ?? where ?? == (P+L)!/P!/L!1L/(P+1)/(P+L) == (P+L)!/(P+L) /P!/(P+1) /L!L == (P+L-1)! /(P+1)! /(L-1)!` [download] 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 `C(P+L,P)C(P+L,P+1)/(P+L) or C(P+L,L)*C(P+L,L-1)/(P+L) or ...` [download] ...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]
Re: Re^2: Parens permutations (formula) by artist (Parson) on Aug 05, 2003 at 20:25 UTC
++tye for generating the excellent formula. Lots of interesting math involved in seemingly simple looking problem. Why the formula make sense is a very good question and I don't have answer at the moment. 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. artist	[reply]
Re^2: Parens permutations (order) by gamzeozl (Initiate) on Jan 22, 2008 at 07:41 UTC
I have to find the table which was obtained by >parenperms 1..7 1..7 parens lengths	[reply]
Re: Parens permutations by Limbic~Region (Chancellor) on Aug 05, 2003 at 05:44 UTC
artist, 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 = 1 permutations = ((n² + n)/ 2) p = 2 let k = ((n² + n)/ 2) permutations = ((k² + k)/ 2) Second problem: There can be some ambiguity in what we are actually grouping: `(1 (2) 3)` [download] Can be seen as either 1 & 3 + 2 or 1 & 2 + 2 & 3. This breaks the formula for p = 2 since: `p = 2 n = 3 k = 6 permutations = 21` [download] 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
I think this could be solved without having to use recursion. Given: m array elements -- e.g. m=3 for qw/1 2 3/ p paren sets -- e.g. p=2 for "(( ))" or "()()" You have m + 1 positions around the array elements, such that: m positions may have 0 .. p open parens (i.e. the final position cannot have any) m positions may have 0 .. p close parens (i.e. the initial position cannot have any) the i-th close paren must be placed in any position to the right of the i-th open paren (i.e. if the i-th open paren is at position j, then the i-th close paren must be at position j+k where k is greater than zero, but less than or equal to 1+m-j). 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]

Back to Seekers of Perl Wisdom