This is an O(n!) because the output is O(n!) - there is no way around it. Still - it can be greatly optimized if we generate the valid combinations in order instead of generating all the combinations and filtering for the valid ones - which both increases the number of combinations we need to generate and forces us to pay for validating each configuration.
First, we need to represent the combinations. It is enough to represent the positions of the opening parenthesis, as we can fill the closing parenthesis when we generate the string. So our data structure will be an n sized vector of positions. The first position is always 0, but we'll keep it in the vector anyway for the sake of simplicity.
What makes a representation valid? The first position - p[0] - must be 0. Technically this means we can just use an n-1 sized vector, but we'll keep it in the vector anyway for the sake of simplicity.
What about the other position? For each k in [1,n), what are the valid values for p[k]? Obviously p[k] > p[k-1] so we have a minimum. The maximum is less obvious but also easy - k * 2. This is the maximum number of characters before it - k opening parenthesis and k closing parenthesis. There cannot be more opening parenthesis because k is the kth, and there cannot be more closing parenthesis because then there won't be enough opening parenthesis to match them.
So, if we have p[0], p[1], ... p[k] we know the valid ranges of p[k+1] - and that's enough to advance p:
structValidParenthesesGenerator{num_pairs:usize,open_paren_locations:Vec<usize>,}implValidParenthesesGenerator{pubfnnew(num_pairs:usize)->Self{Self{num_pairs,open_paren_locations:Vec::new(),}}fngenerate_placement(&self)->String{letmutresult=String::with_capacity(self.num_pairs*2);for&open_paren_indexinself.open_paren_locations.iter(){whileresult.len()<open_paren_index{result.push(')');}result.push('(');}whileresult.len()<self.num_pairs*2{result.push(')');}result}}implIteratorforValidParenthesesGenerator{typeItem=String;fnnext(&mutself)->Option<Self::Item>{loop{letlast=ifletSome(last)=self.open_paren_locations.pop(){last}else{// Special case guard. We put it here as an optimization because we only get here once anyway.ifself.num_pairs==0{returnNone;}// This is the first iteration, so we put 0 as the first index and let the// following `while` loop fill up the rest.self.open_paren_locations.push(0);break;};ifself.open_paren_locations.is_empty(){returnNone;// Cannot move the first paren}letmax_position=self.open_paren_locations.len()*2;// when all previous opening parens are closediflast<max_position{self.open_paren_locations.push(last+1);break;}}whileself.open_paren_locations.len()<self.num_pairs{let&last=self.open_paren_locations.last().expect("After the loop there should be at least one");self.open_paren_locations.push(last+1);}Some(self.generate_placement())}}
On my machine, when built with release, it can generate all 35,357,670 combinations for n=16 in between 4 and 5 seconds. Printing them takes much much much longer - even when I redirect the output to /dev/null it takes half a minute, and when I don't it takes forever (didn't let it finish). I suspect other implementations will have similar problems, so you should try to time them without printing the combinations (just print how many you got)
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 an
O(n!)
because the output isO(n!)
- there is no way around it. Still - it can be greatly optimized if we generate the valid combinations in order instead of generating all the combinations and filtering for the valid ones - which both increases the number of combinations we need to generate and forces us to pay for validating each configuration.First, we need to represent the combinations. It is enough to represent the positions of the opening parenthesis, as we can fill the closing parenthesis when we generate the string. So our data structure will be an
n
sized vector of positions. The first position is always 0, but we'll keep it in the vector anyway for the sake of simplicity.What makes a representation valid? The first position -
p[0]
- must be 0. Technically this means we can just use ann-1
sized vector, but we'll keep it in the vector anyway for the sake of simplicity.What about the other position? For each
k
in[1,n)
, what are the valid values forp[k]
? Obviouslyp[k] > p[k-1]
so we have a minimum. The maximum is less obvious but also easy -k * 2
. This is the maximum number of characters before it -k
opening parenthesis andk
closing parenthesis. There cannot be more opening parenthesis becausek
is thek
th, and there cannot be more closing parenthesis because then there won't be enough opening parenthesis to match them.So, if we have
p[0], p[1], ... p[k]
we know the valid ranges ofp[k+1]
- and that's enough to advancep
:You can see it in action at play.rust-lang.org/?version=stable...
On my machine, when built with release, it can generate all 35,357,670 combinations for
n=16
in between 4 and 5 seconds. Printing them takes much much much longer - even when I redirect the output to/dev/null
it takes half a minute, and when I don't it takes forever (didn't let it finish). I suspect other implementations will have similar problems, so you should try to time them without printing the combinations (just print how many you got)