Coding since 11yo, that makes it over 30 years now ~~~
Have a PhD in Comp Sci ~~~
Love to go on bike tours ~~~
I try to stay as generalist as I can in this crazy wide place coding is at now.
This is another case where dynamic programming is useful.
Refactoring the problem as "Give me all the valid (eg. don't end in an open) parenthesis combos of some given string length which, in aggregate, close some given number of parentheses along their length"
Then we get a nice substructure to work with: the result for some given length is just an easy convolution on the result for a smaller length.
Hmm, that came out a bit confusing.
Hopefully the code is easier to follow...
TypeScript:
constmemoKey=({aggregateCloseCount,length}:{aggregateCloseCount:number;length:number;}):string=>`${aggregateCloseCount}${length}`;constparenPermutationsMemo:{[key:string]:string[]}={};constparenPermutations=({aggregateCloseCount=0,length}:{aggregateCloseCount?:number;length:number;}):string[]=>{// clip away impossible param settings:// if `aggregateCloseCount<0` any string would need to open more than it closes, which would result in an invalid paren combo// if `aggregateCloseCount>length` any string would need to have more close chars than chars overallif(aggregateCloseCount<0||aggregateCloseCount>length)return[];// early exit for `length==0`if(length==0)return[""];constkey=memoKey({aggregateCloseCount,length});return(parenPermutationsMemo[key]||(parenPermutationsMemo[key]=["(",")"].flatMap(prefix=>parenPermutations({length:length-1,aggregateCloseCount:aggregateCloseCount+Number(prefix=="(")-Number(prefix==")")}).map(perm=>prefix+perm))));};constparenPairPermutations=(pairs:number):string[]=>parenPermutations({length:pairs*2});
A couple of runs...
console.log(parenPairPermutations(3));//> Array(5) ["((()))", "(()())", "(())()", "()(())", "()()()"]// The main advantage of this approach is better complexity, coping with higher countsconstgrindTestPairCount=14;console.time(`Time for ${grindTestPairCount} pairs`);console.log(`There are ${parenPairPermutations(grindTestPairCount).length} permutations for ${grindTestPairCount} pairs of parens`);console.timeEnd(`Time for ${grindTestPairCount} pairs`);//> There are 2674440 permutations for 14 pairs of parens//> Time for 14 pairs: 6208.31201171875ms//(old mac pro)
For further actions, you may consider blocking this person and/or reporting abuse
We're a place where coders share, stay up-to-date and grow their careers.
This is another case where dynamic programming is useful.
Refactoring the problem as "Give me all the valid (eg. don't end in an open) parenthesis combos of some given string length which, in aggregate, close some given number of parentheses along their length"
Then we get a nice substructure to work with: the result for some given length is just an easy convolution on the result for a smaller length.
Hmm, that came out a bit confusing.
Hopefully the code is easier to follow...
TypeScript:
A couple of runs...