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

---

---

Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!

Titles consisting of a single word are discouraged, and in most cases are disallowed outright.

Read Where should I post X? if you're not absolutely sure you're posting in the right place.

Please read these before you post! —

• How do I compose an effective node title?
• How do I post a question effectively?
• Markup in the Monastery

Posts may use any of the Perl Monks Approved HTML tags:

a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr

You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)

	For:		Use:
	&		&
	<		&lt;
	>		&gt;
	[		&#91;
	]		&#93;

Link using PerlMonks shortcuts! What shortcuts can I use for linking?

See Writeup Formatting Tips and other pages linked from there for more info.