good chemistry is complicated,and a little bit messy -LW PerlMonks

Parens permutations

by artist (Parson)
 on Aug 02, 2003 at 21:02 UTC Need Help??
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

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)
```
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.

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
```
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]```
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...

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

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!]^2*1*L/(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!]^2*1*L/(P+1)/(P+L)
== [ C(P+L,P) ] * ??
where
?? == (P+L)!/P!/L!*1*L/(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
++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.

I have to find the table which was obtained by >parenperms 1..7 1..7 parens lengths
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 = ((n2 + n)/ 2)

p = 2
let k = ((n2 + n)/ 2)
permutations = ((k2 + 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

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).

Log In?
 Username: Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://280334]
Approved by hsmyers
Front-paged by broquaint
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others musing on the Monastery: (4)
As of 2018-02-19 08:55 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
When it is dark outside I am happiest to see ...

Results (260 votes). Check out past polls.

Notices?