10
\$\begingroup\$

Given a number n, print all correct parenthesis sequences of parentheses and square brackets of length \$n\$ in lexicographical order. You must enter an integer \$n\$ from 0 to 16 inclusive. The output should be "Print all valid parenthesis sequences of length n parentheses and square brackets in lexicographical order. Each sequence should be printed on a new line"

I have code that works and does everything correctly

#include <iostream>
#include <vector>
#include <string>
#include <stack>

using namespace std;

bool isValid(const string& s) {
    stack<char> st;
    for (char c : s) {
        if (c == '(' || c == '[') {
            st.push(c);
        } else {
            if (st.empty()) return false;
            char top = st.top();
            st.pop();
            if ((c == ')' && top != '(') || (c == ']' && top != '[')) {
                return false;
            }
        }
    }
    return st.empty();
}

void generateSequences(int n, string& s, vector<string>& result) {
    if (s.size() == n) {
        if (isValid(s)) {
            result.push_back(s);
        }
        return;
    }

    s.push_back('(');
    generateSequences(n, s, result);
    s.pop_back();

    s.push_back('[');
    generateSequences(n, s, result);
    s.pop_back();

    s.push_back(')');
    generateSequences(n, s, result);
    s.pop_back();

    s.push_back(']');
    generateSequences(n, s, result);
    s.pop_back();
}

int main() {
    int n;
    cin >> n;

    if (n % 2 != 0) {
        return 0;
    }

    vector<string> result;
    result.reserve(1 << n);
    string s;
    s.reserve(n);

    generateSequences(n, s, result);

    for (const string& seq : result) {
        cout << seq << endl;
    }

    return 0;
}

I can't figure out how to optimize the code. Our university's compiler says that my code runs in 2,089 seconds, but it should run in less than two seconds. Really funny picture...

So I want to know how to optimize the code so that it runs faster than 2 seconds

\$\endgroup\$
14
  • 2
    \$\begingroup\$ Suggestion (only): is_valid() is using stack operations that could be simply replaced with two up/down counters and an iterative loop. Try it on paper. If either counter dips below zero before the end of the string, or is non-zero upon reaching end of string, then the string is invalid... Faster termination of checking most of the gazillion strings generated... (If you're really clever, you can sense-and-avoid generating improper strings, nipping the problem in the bud, and save a whole-bunch of pointless processor cycles. "Algorithm", not "brute force to the end of each branch".) \$\endgroup\$
    – Fe2O3
    Commented Jun 7 at 2:19
  • 2
    \$\begingroup\$ Please verify tagging of your question. If your code is written to C++ 2020, please do not use the [c++17] tag. If it fits version 2017 and does not use 2020 features, do not use [c++20]. \$\endgroup\$
    – CiaPan
    Commented Jun 7 at 12:08
  • 2
    \$\begingroup\$ "my code runs in 2,089 seconds" Is that comma a thousands separator or a decimal separator? Is it a bit over two seconds, or a bit over two thousands seconds? \$\endgroup\$ Commented Jun 7 at 21:30
  • 2
    \$\begingroup\$ @Fe2O3 The accepted answer seems to be a review: Avoid boilerplate code, replace duplicated pieces of code (OP code is not DRY). It was not the best question. The OP has also asked 3 more questions since posting this one. \$\endgroup\$
    – pacmaninbw
    Commented Jun 8 at 23:02
  • 1
    \$\begingroup\$ @Fe2O3 Are you aware of The 2nd Monitor? Most of the CR moderators spend some time there. Good place for discussions. \$\endgroup\$
    – pacmaninbw
    Commented Jun 9 at 11:38

8 Answers 8

8
\$\begingroup\$

Avoid boilerplate code. Replace duplicated pieces with a range-based for loop over an initializer list:

void generateSequences(int n, string& s, vector<string>& result) {
    if (s.size() == n) {
        if (isValid(s)) {
            result.push_back(s);
        }
        return;
    }
    for (char c : {'(', '[', ')', ']'}) {
        s.push_back(c);
        generateSequences(n, s, result);
        s.pop_back();
    }
}

The proposed brute-force algorithm is the issue because it has time complexity of O(n * 4ⁿ) (it is the big theta actually). For n = 16, the total number of steps is huge, probably about 6✕10¹⁰. There is a straightforward recursive approach that does not rely on the verification,

void generateImpl(int openLimit, stack<char> open, string seq, vector<string>& result) {
    if (openLimit > 0) {
        open.push('(');
        generateImpl(openLimit - 1, open, seq + '(', result);
        open.top() = '[';
        generateImpl(openLimit - 1, open, seq + '[', result);
        open.pop();
        if (!open.empty()) {
            char op = open.top();
            open.pop();
            if (op == '(')
                generateImpl(openLimit, open, seq + ')', result);
            else
                generateImpl(openLimit, open, seq + ']', result);
        }
    }
    else {
        for (; !open.empty(); open.pop())
            seq += (open.top() == '(') ? ')' : ']';
        result.push_back(seq);
    }
}

vector<string> generateSequences(int n) {
    if (n % 2 == 1) return {};
    vector<string> result;
    generateImpl(n / 2, {}, {}, result);
    return result;
}

The code above is self-explanatory and runs many times faster. The times are around 450 ms for n = 14 and 3532 ms for n = 16 on my pc. The brute-force solution takes around 555568 ms for n = 14, and it is still running for about an hour for n = 16.

The code works fine for n=16, but could be further optimized for larger inputs.

\$\endgroup\$
4
  • \$\begingroup\$ Thank you very much! You helped a lot with the problem and now I understand how to work with similar problems! \$\endgroup\$
    – Dmitry
    Commented Jun 7 at 23:33
  • \$\begingroup\$ Nice algorithm. It's "apples and oranges"... The OP's code outputs its collection of strings, but we don't know if the OP's timings (on what kind of hardware?) include or exclude producing the output. For reference, are these timings inclusive of the output (perhaps to a file, not stdout)? "Benchmarking" results should also state the optimisation used when compiling. \$\endgroup\$
    – Fe2O3
    Commented Jun 8 at 21:11
  • \$\begingroup\$ @Fe2O3 they don't include the output. These numbers are merely estimates to demonstrate the poor time asymptotics. \$\endgroup\$
    – panik
    Commented Jun 9 at 0:16
  • \$\begingroup\$ It's the OP's code that's to be reviewed... but... I can't help noticing the 2 pairs of recursive calls to the function. The only difference between each of either pair is a single character being appended to seq. Just a friendly suggestion to consider DRY and reduce 4 lines down to 2... Cheers! \$\endgroup\$
    – Fe2O3
    Commented Jun 18 at 9:04
10
\$\begingroup\$

Check standard input for error:

int n;
cin >> n;

It can be as simple as:

if (!std::cin) {
    std::cerr << "Input failed\n";
    return EXIT_FAILURE;
}

Broken implementation:

The specification states:

You must enter an integer $n$ from 0 to 16 inclusive.

But your check:

if (n % 2 != 0) {
    return 0;
}

does not take the range into account, the above would allow integers greater than 16, as well as negative ones.

Print a helpful error message:

If the input was not an even number, you exit with a successful exit code (which should really have been EXIT_SUCCESS from <cstdlib>) without printing any error message. How would I ever know how to use the program if there is not even a usage message?

The specification might have not mandated that, but it helps.

Do not flush standard output after printing each string:

for (const string& seq : result) {
    cout << seq << endl;
}

std::endl flushes the underlying buffer along with printing a newline. The flushing is not required here, and this should be replaced with a simple '\n'. The standard streams are automatically flushed on program exit.

And you can omit return 0, as that is the default behavior.

See also: What's the problem with "using namespace std;"?.

And this:

s.push_back('(');
generateSequences(n, s, result);
s.pop_back();

s.push_back('[');
generateSequences(n, s, result);
s.pop_back();

s.push_back(')');
generateSequences(n, s, result);
s.pop_back();

s.push_back(']');
generateSequences(n, s, result);
s.pop_back();

calls for a loop, or a separate function.

\$\endgroup\$
2
  • \$\begingroup\$ "If the input was not an even number, you exit with a successful exit code ... without printing any error message" isn't this just exactly in-spec for the given problem? All solutions were successfully output, after all. \$\endgroup\$
    – ManfP
    Commented Jun 7 at 20:53
  • \$\begingroup\$ @ManfP Better now? \$\endgroup\$
    – Harith
    Commented Jun 8 at 1:37
7
\$\begingroup\$

Well, I think the main idea should come from the algorithm improvement. You generate a lot of wrong sequences, and you generate them all the way to the end, only to then go through the sequence again and discard it as invalid.

In other words, for a given n, your algorithm always generates and checks all 4ⁿ sequences. And this with recursive calls for each, which adds to the slowness.

Instead, you should focus on stopping a generation stream as soon as you go away from the correct sequence. For example, if s = '(((' and now you're on the 4th recursive call, then s.push_back(']') is clearly a wrong operation. Nor should you generate any of the remaining 4¹² other invalid sequences that have (((] as initial substring.

\$\endgroup\$
7
\$\begingroup\$

IMO, you have tried to brute-force your way too early in your dev process. I mean no offense but there is no intelligence in building strings by exploring all possible possibilities at every step.

There is a number of properties you have not used in your code that could greatly speed up things:

  1. A valid sequence must start with ( or [ and it must end with ) or ].
    It does not look like much but this disqualifies 50% of the random sequences your code generates at the very first character.
    More than half of your total execution time that could be solved with just 2 lines of code; there is honestly no good reason not to do that.
    50% of what remains can be disqualified by only looking at the last character.

  2. In any substring starting from the left of the sequence, there cannot be more ) than ( nor can there be more ] than [. Importantly and as others have said, this is something you can test in the middle of constructing the sequences.
    Similarly, in any substring ending at the right of the sequence, there cannot be more ( than ) nor more [ than ] (to be fair, I did not manage to use this property either but I am sure I could with a little bit of effort).
    You probably only need 2 counters to ensure you stay within both constraints.

    • First counter: Start at n/2, decrease it when placing a (/[. When equal to 0, you can only append ) or ] (better yet, make use of property 3 below to directly complete the sequence without doing any additional exploration).
    • Second counter: Start at 0, increase it when placing a (/[, decrease if when placing a )/]. When its value is 0, you can only place ( or [.
  3. Taking a step back and trying to tackle the problem myself, I think is my most important realization is this:

    There are, really, only 3 characters needed to build a sequence: (, [ and _, where _ is a placeholder for ) or ].
    If I give you the following string, where only the placement of ( and [ is known: ([(__(_[__, then the only way to replace the placeholders to complete the sequence is: ([()]()[]).
    Again, this looks like a small optimization but it can help big time: your recursion would not need to explore 4 branches at every step but 3, making your algorithm at worst O(3^n) (in fact probably better thanks to property 2 above) instead of O(4^n) (for reference, 3¹⁶ = 43,046,721 vs 4¹⁶ = 4,294,967,296‬ - about 100✕ more).

  4. There might be a way to generate some/all sequences of length n from sequences of length n-2, even if not in order. Your question lacks any description regarding your attempt to find a pattern in the sequences.
    To be clear, whether you were successful or not, you should have tried to find one and described your attempt here and why you think you failed so we could have helped on that.

On the other hand, what you did correctly is to not allow the ( and [ to be permuted in the sequences. Allowing that tends to create situations where e.g. the first 2 ( are swapped, which means you are working on 2 duplicates.
I am not sure you purposely avoided that but yes, that was good.


What I have done for my alternative implementation:

  1. Count from 0 to 2ⁿ-1 and generate the corresponding sequence of opening brackets ((/[) based on each number binary representation.

  2. Generate a pattern in the form of ...___ where the . represent opening brackets and the _ represent closing brackets.

  3. Generate the valid permutations of the above representation.

    The main goal here is to avoid generating as many invalid sequences as possible. To achieve that, I used the fact that the first and last characters will not be permuted, and knowledge that the _ "travel" from the right to the left, to detect when a closing bracket reaches the 2nd position (i.e. its leftmost valid position) and narrow down what needs to be permuted on the next loop (if the 2nd character is a closing bracket, then the 3rd character must be an opening bracket and only the 4th character onward can be permuted from this point), and do it repeatedly.

  4. Sequences are then ordered before printed in what I hope is your lexicographic order (you have no described the precise rule so it is done using ASCII values by default).

The code generates 366080 sequences of size 16 and I have not spotted any invalid ones but cannot fully guarantee it is bug free.

Snippet:

int n = 16, half = n/2;
if (half * 2 != n) // Is n odd?
    return 0;

auto close = [n](const std::string& input, const std::string& pattern) -> std::string {
    std::string result; result.reserve(n);
    auto i = input.begin();
    for (auto c : pattern) {
        if (c == '.') {
            result.push_back(*i);
            std::advance(i, 1);
        }
        else {
            int count = 0;
            for (auto r = result.rbegin(); r != result.rend(); ++r) {
                if (*r == ')' || *r == ']')
                    count += 1;
                else if (count == 0) {  
                    if (*r == '(')
                        result.push_back(')');
                    else
                        result.push_back(']');
                    break;
                }
                else
                    count -= 1;
            }
        }
    }
    return result;
};

std::vector<std::string> results;

std::string p;
p.resize(half, '.'); p.resize(n, '_');

for (int i = 0; i < (1 << half); ++i) {
    std::string pattern = p, str;
    //Generate the ordered opening brackets
    for (int j = 1 << (half - 1); j >= 1; j >>= 1)
        str.push_back((i & j) ? '[' : '(');
    
    //The first and last characters are fixed; we won't allow them to be permuted.
    auto begin = std::next(pattern.begin()), end = std::prev(pattern.end());
    do {
        std::string print = close(str, pattern);
        auto s = print.size();
        //The only control we need to do is the size: if wrong, that means the function could not reconstruct ) and ] from the input
        if (print.size() == n)
            results.push_back(print);
        if (*begin == '_') // Getting a _ here means we must narrow the portion of pattern we can permute
            std::advance(begin, 2);
    } while (std::next_permutation(begin, end));
}

std::sort(results.begin(), results.end());
for (auto s : results)
    std::cout << s << '\n';
\$\endgroup\$
0
5
\$\begingroup\$

In addition to the other good answers here:

  1. Please don't drag the whole of std into the global namespace with using namespace std; - that completely eliminates all the benefits of namespacing and makes your code less predictable.

  2. Be especially careful with names such as isValid - a C reviewer would likely reject this at review for using a reserved identifier; in C++, only the names in std:: are reserved, but headers such as <cctype> are allowed to declare global-namespace versions of the same function, so we should take notice in C++ too. This particular reserved name is a group that begin is followed immediately by a letter, so we could simply rename to is_valid, for instance.

  3. The problem statement is very vague as to what it considers to be "lexicographical order". It may be worth including comments to explain your interpretation, particularly if that relies on a particular runtime character coding.

    If we need to adapt to the user's locale, we could find the correct ordering like this:

     auto const& locale = std::locale("");
     std::string parens{"[]()"};
    
     auto locale_less = [&locale](char a, char b) {
         std::string sa{ a };
         std::string sb{ b };
         return locale(sa, sb);
     };
    
     std::ranges::sort(parens, std::less<char>{}); // in case locale compares equal
     std::ranges::sort(parens, locale_less);
    
  4. We don't need to do any work at all if the requested length is an odd number, as all odd-length strings are invalid. So we're correct to exit early with no output, rather than producing all possible odd-length strings and rejecting them one by one.

  5. return 0; is optional in the main() function, so we can simplify the code by omitting it.

\$\endgroup\$
0
4
\$\begingroup\$

After having some fun with this, here is a response for the OP to consider.

Paraphrasing the problem statement, input will range from 0 to 16. Use this value to generate, in "sorted order" only "correct" strings comprised of '(', ')', '[' and ']'.

The first thing to notice is that the value MUST refer to 0 - 16 pairs of characters.
(By definition, a string with an odd length cannot contain matching pairs of characters.)

Checking an ASCII chart, we find parentheses rank ahead of square brackets. This much is easy.

Consider the case for 1 (pair).
The solution is "()" and "[]"

The solution for 0 is "" (an empty string).

Just a few more to go...


Review:

The OP's code is well structured and nicely formatted.
Its algorithm, however, is badly in need of improvement.
Generating all possibilities, and then screening each for compliance, is exponentially wasteful.
For all their advantages, and recognising their provenance is the gurus who live atop the mountains, library solutions can only be used as they were designed to be used. "One size fits most." It can be difficult to peer into the black box.

CS academics refer to "Big O notation", that reflects one of two attributes of an algorithm: "Time Complexity" and "Space Complexity". Optimising for either tends to punish the other; often an inescapable trade-off.

A third "complexity" (in the workplace) is "Cost Complexity". The most elegant approach may be viewed as a work of art by all who might be awed by it, but business has a difficult time funding a week's development of code to solve a one-time problem that could be coded "cheap-and-dirty" in an hour-or-two. O($) vs O(n$3) A further trade-off.

The OP's code is claimed to work, but "is too slow".
How much effort (what "cost") would be required to make the program run faster?


Below is some C source that I believe could speed-up completion of execution. (Not benchmarked, but presented for the OP to consider, complete and test in their environment.)

While compilers have come a long way, the frequent instantiation of objects and opaque performance of, for instance, the OP's 'stack' evaluation of the (potentially) gazillion generated strings, gives one the impression that greater speed might be achievable with a purpose-built algorithm. (Below is a humble offering; one of perhaps several alternatives.)

The greatest saving, imo, would come from early detection that an arrangement of symbols being assembled will not satisfy the criteria, and then abandoning that attempt to move on the the next possibility. "Pruning the tree of possibilities" on-the-fly.


#include <stdio.h>
#include <stdint.h>

typedef uint32_t u32; // brief
typedef uint64_t u64; // brief

const int PAIRS = 2 * 16; // up to 16 pairs eventually

static enum {
    elp = 0x0, // 0b00 '('
    elb = 0x1, // 0b01 '['
    erb = 0x2, // 0b10 ']'
    erp = 0x3, // 0b11 ')
};

static void showIfValid( u64 s, u32 n ) {
    /*
     * TBD: Screen out invalid arrangements of symbols
     */
    char buf[ PAIRS + 1 ] = {0};
    u32 i = PAIRS;
    for( ; n--; s >>= 2 )
        buf[ --i ] = "([])"[ s & 0x3 ];
    puts( buf + i );
}

static const u32 lex[] = { elp, erp, elb, erb };

static void gen( int n, u64 s, int lvl, int np, int nb ) {
    if( lvl++ == n ) { // base case
        showIfValid( s, n+n );
        return;
    }

    for( u32 ix = 0; ix < 4; ix++ ) {
        u32 x = lex[ ix ];
        int npx = np, nbx = nb;

        if( x == erp ) {
            if( npx == 0 ) continue; // more ')' than '(' is invalid
            npx--;
        }
        else if( x == erb ) {
            if( nbx == 0 ) continue; // more ']' than '[' is invalid
            nbx--;
        } else {
            if( ( np + nb ) >= n ) continue; // more that 1/2 are lefts! Too many!
            npx += x == elp;
            nbx += x == elb;
        }

        for( u32 iy = 0; iy < 4; iy++ ) {
            u32 y = lex[ iy ];
            int npy = npx, nby = nbx;

            if( y == erp ) {
                if( npy == 0 ) continue; // more ')' than '(' is invalid
                npy--;
            }
            else if( y == erb ) {
                if( nby == 0 ) continue;  // more ']' than '[' is invalid
                nby--;
            } else {
                if( ( np + nb ) >= n ) continue; // more that 1/2 are lefts! Too many!
                npy += y == elp;
                nby += y == elb;
            }
            u64 sy = (s << 4) | ((x << 2) | y);

            gen( n, sy, lvl, npy, nby );
        }
    }
}

int main( void ) {
    for( u32 n = 1; n < 3; n++ ) { // for now, generate just 1 & 2 pairs
        u64 s = 0;
        gen( n, s, 0, 0, 0 );
        puts( "********" );
    }
    return 0;
}

Result:

((
()   <-- valid
([
[(
[[
[]   <-- valid
********
(())   <-- valid
()((
()()   <-- valid
()([
()[(
()[[
()[]   <-- valid
([)]
([])   <-- valid
[()]   <-- valid
[(])
[[]]   <-- valid
[]((
[]()   <-- valid
[]([
[][(
[][[
[][]   <-- valid
********

Notes:

For 1 pair, without the "correct" criteria, there are 16 combinations possible. This code culled 10 of 16, leaving 6 for further evaluation before being accepted for printing.

For 2 pair, this code completed generating 18 of, potentially, 64 combinations. This algorithm saved having to evaluate 64-18=46 other impossible combinations.


Code explained:

Fundamental: a program's internal data representation does not have to be exactly the same values as is represented outside of the program. This code works with bits representing 4 symbols. It is only when a target combination of those symbols is output that each symbol is translated to satisfy the problem statement.

It's fortunate that the problem statement wants "up to 16 pairs made from 4 symbols". Two bits is enough to represent each unique symbol. A "pair" will require four bits. Up to 16 "pairs" requires up to 64 bits. One uint64_t variable is sufficient to satisfy the requirement of holding one potential pattern.

When generating a pattern, an outer loop iteratively proposes one of the 4 symbols (as a two-bit binary value). For each of those, an inner loop then iteratively proposes a second symbol (two more bits).

A few counters perform a preliminary screening of each proposition to detect (early) and possibly reject assembling an entire collection of symbols that has no chance of being correct. ("Pruning the possibility space.") (More attention to this phase would be valuable, although it seems to be working so far.)

When the recursion has assembled a candidate sequence of two-bit pairs, the candidate (as a 64 bit variable) is passed to another function for final evaluation (to be done) and possible output.


Care and attention and completion:

The one-to-one assignment of bit patterns has been chosen to:

  • aid sorting by developing assemblies in lexicographic order,
  • allow summing of adjacent symbols to find sum = 3 (see below)

The unfinished TBD screening envisioned by the coder is an intricate series of shift and mask and or operations that iteratively excise adjacent 'complementary' pairs from the proposed assembly. In so doing, a correct assembly will evaporate to nothing, and an incorrect assembly will stubbornly refuse further shrinkage. (Not necessarily the fastest approach, but it will be fun to code on another day.)

If interested, the OP has some work to do.


Future development:

Examine the two samples of output shown. Notice something?

Eventually [ drifts to the left across the mid-way point of the strings so far approved for output.

Theory: buffering approved strings that are output would allow the program to detect this transition and simply "play back" in reverse those buffered strings AFTER appropriately swapping each character with its curved or square counterpart. It might not be necessary to work too hard for the second half of the output! Worth a try??

The astute reader will recognise that the "buffer" array would be an array of uint64_t variables, and an alternate decode to ASCII string would be simple to use...


Performance insight:

When thinking about filtering/reducing a candidate's internal representation to determine its "correctness", the intention was to use shifting and masking to locate adjacent symbols that "paired-up"; eg: "()" or "[]". Iteratively, each of these pairs would be removed by more shifting and masking and or'ing until the valid candidate disappeared and its preserved copy could be output.
Incorrect candidate sequences would eventually resist further shrinkage; that candidate would not be output.

For example:

()() => "" => Valid => output original
([]) => () => "" => Valid => output original
([)] => ([)] => stuck! => Invalid => not output

Rare correct instances analogous to "(((())))" will require a few iterations to evaporate.

To speed-up shrinkage, it is worth noting that there are two more legitimate pairings of adjacent characters that can be eliminated, reducing the number of iterations to be performed.

Recognise that "][" and ")(" are pairings that can be eliminated/excised when found, but ONLY when such a pair is NOT at EITHER end of a candidate.

"[()][()]" => "[]" => "" => Valid. "()", "][", and "()" excised on 1st iteration.

The OP's problem statement is turning out to be a challenge with unforeseen depth and interesting possibilities, imo.

\$\endgroup\$
8
  • \$\begingroup\$ The only problem I have with your answer is that the OP is using C++ rather than C, any alternate solution should probably also be in C++. \$\endgroup\$
    – pacmaninbw
    Commented Jun 7 at 12:13
  • \$\begingroup\$ @pacmaninbw Fair criticism. I believe this code will compile cleanly with a C++ compiler. Perhaps its single data output statement could be change to some form of cout << yadda; (In point of fact, my file is "fun.cpp" and compiled with a C++ compiler...) If the OP, or the reader, is certain that some of the functionality shown is available from a C++ library, they are welcome to swap out/in the relevant part. (My motivation is to encourage the OP to NOT become reliant on a library/class offering 150+ tested methods. A coder should know what the bits & bytes are doing.) Cheers! :-) \$\endgroup\$
    – Fe2O3
    Commented Jun 7 at 12:19
  • \$\begingroup\$ If the desired length is 0-16, doesn't that make 0-8 pairs? \$\endgroup\$ Commented Jun 7 at 15:13
  • \$\begingroup\$ Parens do rank ahead of square brackets on ASCII systems using the "C" locale, but that's not necessarily the case for all users. If we want to be thoroughly rigorous, perhaps we should do a trial comparison such as strcoll("(", "]") to determine the ordering to use. Or even, sort an array of {'(', ')', '[', ']'} using a strcoll-based comparison function? (Probably with a fall-back to numeric comparison for locales where some/all of these compare equal). \$\endgroup\$ Commented Jun 7 at 15:17
  • \$\begingroup\$ @TobySpeight Re: "8 pairs vs 16 pairs". I think you're right. I'm glad this code should work for 16, and for 8, too. :-) Sometimes, I disagree with how problems are phrased, and possible misinterpretation. Struck me as odd that "how to deal with 'n' being odd" is not in the problem statement. The directions form a paradox. "Do this, do it correctly, but do it when 1/2 the cases will be incorrect... ??? \$\endgroup\$
    – Fe2O3
    Commented Jun 7 at 20:50
3
\$\begingroup\$

I try to avoid answers here that propose starting over from scratch, but in this case, that is the correct answer to the open-ended question you asked.

Generate the Sequences in Lexicographic Order

You want to use a backtracking search, which could either be recursive or a loop using a stack data structure as a trampoline.

The first step should be to generate every balanced set of a single type of delimiter. For the moment, I’ll call them { and }. A string of 2M balanced delimeters has M opening braces and M closing braces, so you can specify any valid sequence as the positions of the M } symbols, from front to back. (Since 2M is constrained to be less than 256, a std::array<uint8_t, M> would be an efficient data structure to use.)

Now, consider the following facts:

  1. Any } symbol closes a unique corresponding { if it is preceded by more { than } symbols in the string: whenever this is the case, there is at least one unclosed { symbol that it closes.
  2. Every symbol in the string is either { or }. The i-th } from the left is always preceded by i-1 } symbols.
  3. Therefore, the i-th } properly closes a corresponding { if and only if it is at position 2i-1 or later.
  4. A string of 2M { and } delimiters is balanced if and only if it has exactly M opening and exactly M closing symbols, and every } symbol closes one unique preceding { symbol.
  5. Therefore, the entire string is balanced if and only if the relation in point 3 holds for every } from number 1 to number M.
  6. Additionally, any valid solution must have space for all remaining M - i } symbols to the right of the i-th }. You can prune all branches of the search tree that run out of space to the right.

Because strings where ( symbols appear before ) symbols or [ symbols appear before ] symbols come first in lexicographic order, you want to first generate every balanced string where the first closing delimiter appears as late as possible (position M of a zero-based array); then all balanced strings where the first closing delimiter appears at the next-latest position, which is M - 1; and so on up to the earliest possible position, which is 1. For each of these cases, you want to place the second } as late as possible first, find all balanced strings beginning with that initial sequence, and then backtrack and move the second } forward one position at a time, and so on.

Now, after having found a balanced string of { and }, it corresponds to 2^M solutions; each of the M pairs of delimiters could be either ( and ), or [ and ]. To generate all of these, given a list of the positions of all M } symbols in your balanced string of braces:

  1. For each } from left to right, find the corresponding { symbol to its left that has not already been closed.
  2. For each number B from 0 to 2^M - 1, replace the i-th { with [ if the i-th-most-significant bit of B is 1, or ( if that bit is 0. Similarly, replace the i-th } with ] if the i-th-most significant bit of B is 1, or ) if that bit is 0.
  3. Since you have a list of the positions of each } from left to right and each } from left to right, the most efficient way to do this is to loop from 0 to M-1, test the appropriate bit of B with a bitwise or, and look up the index of the characters to set to [ or ( and ] or ) from the arrays of positions.
  4. Remember that ( precedes [ and ) precedes ] in lexicographic order.

Finally, bear in mind that because ) precedes [ in lexicographic order, you must actually store all the patterns of balanced { and } so that you can generate only solutions whose initial substring of ( and ) did not change between the current and previous iterations, and get the rest in due time.

That is, you need to generate in lexicographic order every balanced string with no square brackets, then those whose last pair of delimiters are square brackets, then those whose second-last is, then those whose last two are, and so on. You can do this based on the bits of the sequence { 0b00, 0b01, 0b10, 0b11, ..., 0b11111111 }, and the stored list of all balanced strings of braces in lexicographic order.

This is the fly in the ointment with my algorithm: there is a combinatorial explosion of the number of such balanced strings. I suspect this is why the assignment specified a length of 16 or less (or as I described it, M ≤ 8).

A good data structure to store these sequences in C++17 would be a std::vector of the array of positions (which might be a std::array<uint8_t, M> or a struct of two such arrays, one for the positions of } and another for the positions of {, so that you only need to calculate the positions of opening braces once).

\$\endgroup\$
4
  • \$\begingroup\$ With my pedantic hat on, I guess it's (theoretically) possible to have a locale where ) sorts before ( or ] before [. I think it's a fairly safe assumption that it doesn't exist, though! \$\endgroup\$ Commented Jun 9 at 11:51
  • 1
    \$\begingroup\$ @TobySpeight Document the lexicographic order the function uses, I guess? If you’re allowed to pick an arbitrary one, ( < [ < ) < ] would be so convenient. :) \$\endgroup\$
    – Davislor
    Commented Jun 9 at 16:31
  • \$\begingroup\$ { < ( < [ < < < > < ] < ) < } if we could only revise the 60+ y.o. ASCII table, eh? :-) \$\endgroup\$
    – Fe2O3
    Commented Jun 13 at 12:16
  • \$\begingroup\$ @Davislor I've come back to re-read this and read it twice, now. I sense that you're onto something, but... forgive my shrinking brain. Apart from the binary progression, I'm failing to grasp the concept and how it could be coded... I've had fun ruminating on the OP's challenge (time to fill) arriving at the code (golf) I posted today. If you've time to code your method (C or C++), I expect it would receive LOTS of attention! It's a silly thing. I try to think of a practical use and come up dry. But, coding is fun, so... :-) Cheers! (My next version will be for 3 or 4 species of braces.) \$\endgroup\$
    – Fe2O3
    Commented Jun 16 at 8:35
2
\$\begingroup\$

Version 2...

As other answers have noted, the problem statement referring to "length 0-16" is unfortunate and may cause unnecessary difficulty. imo, stating "0-8 pairs" would have been more sensible.

Further, "correct ... sequences of parentheses and square brackets" does not use the more descriptive
"well-formed sequences". The string "((((" is not "incorrect" as it is a string of parentheses, but it is not "well-formed" by the criteria of "nested pairs of () or [] characters".

I will not repeat my other terse review of the OP's code, or duplicate the VG commentary already present in other answers.


The OP has tagged 3 releases of C++ standards. It is my belief that the following code would comply with all of those, and would compile relatively cleaning. There are some differences between C and C++, and the latter may be considered, in many ways, a superset of the former. The code below has been compiled as C++ source on my system (without a problem.)


My other answer suggests a mechanism to detect and prevent the executable from needlessly completing the generation of "impossible strings". This may be an acceptable speed-up if the OP wishes to copy/compile & benchmark that version. Further, described, but not coded, is a suggestion that might speed-up detection (and rejection) of any not-well-formed strings that have been generated.


Another answer presents what appears to be a very clean and efficient (and recognisably C++) solution to the OP's problem.

My concern is that it relies on (undoubtedly correct and tuned) Library "classes" that are, to mere mortals, accepted as working "black boxes". Without delving into the source code of those Library classes, one must simply 'trust' that they are efficiently dealing with dynamic allocation of memory for storage. Does the stack class allocate "one more level" for each push()? Does it release memory for each pop()? Is there a 'knee' that will affect graphing of "speed versus length" for the problem?

Optimistic coders tend toward making "optimistic tests". Lengthy development time may prove to have been inappropriate when real stress testing is applied. This is akin to the "well-formed string" problem herein; coders spending time writing code that must be rejected when fully stressed (tested), and another development path found and followed. (aka, "find a better algorithm".)

Do those "black box" classes contain any performance surprises when used in an application. Was "quick, simple and generic" a wrong path in this instance?


The code below is terse and "bare bones". It has a built-in 'ceiling' of a maximum of 16 pairs of "()" and/or "[]". It uses counters, bits as flags that are shifted right and left, and instances of a small-ish struct in combination with the program's stack (rather than instances of stacks in the application's data space.)

(Note: Should one want to go beyond the limit of 16 pairs, that struct could be made into a C++ class with constructors and operator overloading without too much difficulty.)

With output suppressed (as presented below), the binary runs PDQ on my system, and reports having generated 366080 well-formed variations. OP benchmarking is at the OP's discretion.

A separate "simple minded" block of code translates the "strings" as digits instead of parentheses and brackets. This string of digits is then compared to check each is in ascending sequence. I've checked this up to the OP's criteria of "maximum length = 16".


#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>

static const uint32_t N = 8; // number of pairs to gen for this run
static const uint32_t PAIRS = 2 * 16; // up to 16 pairs
static uint32_t cnt; // count of well-formed strings gen'd

typedef struct { uint64_t s; uint32_t n, rem, o, no; } prm;

static void gen( prm *p ) {
    static const uint32_t oX = 0x00000001, oY = 0x00010000; // 16 + 16 bits as flags

    for( uint32_t i = 0; i < 4; i++ ) { // try 4 characters in ascending order
        prm w = *p; // working copy (reset on each iteration)
        if( i & 1 ) { // odds are close characters
            if( !(w.o & ((i==1)?oX:oY)) ) continue; // closing X or Y not allowed
            w.o = (w.o & ~(oX|oY)) >> 1; // neutralize this open. its close follows
        } else { // evens are open characters
            if( ++w.no > w.n ) continue; // Too many?
            w.o = (w.o << 1) | ( (i==0)?oX:oY ); // record this open
        }
        w.s = (w.s << 2) | i; // good so far. Record character.
        if( --w.rem != 0 ) gen( &w ); // recurse?
        else { // else base case
            cnt++;
            char buf[ PAIRS + 1 ] = {0}, *c = buf + PAIRS;
// use only ONE of these two blocks (or none)
#if 0 // suppress labourious output (improve on this?)
            for( w.n <<= 1; w.n--; w.s >>= 2 ) // translation
                *(--c) = "<>[]"[ w.s & 0x3 ]; // using "<>[]" vs "()[]" for clarity
            printf( "%7d %s\n", cnt, c ); // output
#endif
#if 1 // validation of "lexigraphic order"
            static char prev[ PAIRS + 1 ];
            for( w.n <<= 1; w.n--; w.s >>= 2 ) // translation
                *(--c) = "1234"[ w.s & 0x3 ];
            if( strcmp( prev, c ) < 0 ) strcpy( prev, c );
            else {
                fprintf( stderr, "Failed on %s not LT %s\n", c, prev );
                exit( 0 ); // who cares...
            }
#endif
            return;
        }
    }
}

int main( void ) {
    prm p = { 0, N, N+N };
    gen( &p );
    printf( "N = %d, count = %d\n", N, cnt );
}

Because the comments and two optional blocks of code give the appearance of a horrendous mess, below is the same code "cleaned up" by the author (who knows what single character variable names are used for.) This version generates the desired strings and only reports the count of those it would have output.

// same headers, vars and typedef omitted for brevity

static void gen( prm *p ) {
    static const uint32_t oX = 0x00000001, oY = 0x00010000;

    for( uint32_t i = 0; i < 4; i++ ) {
        prm w = *p;
        if( i & 1 ) {
            if( !(w.o & ((i==1)?oX:oY)) ) continue;
            w.o = (w.o & ~(oX|oY)) >> 1;
        } else {
            if( ++w.no > w.n ) continue;
            w.o = (w.o << 1) | ( (i==0)?oX:oY );
        }
        w.s = (w.s << 2) | i;
        if( --w.rem != 0 ) gen( &w );
        else { cnt++; /* output OR check can go here */ return; }
    }
}

// same main()

And there's extreme succinctness (that some readers may regard as "Code Golf") that provides a reasonable demonstration of the power of C. Being this compact, a large and detailed comment block would be required to explain the steps and operations of each line of compiled source code.

static void gen( prm *p ) {
    static const uint32_t oX = 0x00000001, oY = 0x00010000;

    for( uint32_t i = 0; i < 4; i++ ) {
        prm w = *p;
        if( (i & 1) == 1 && !(w.o & ((i==1)?oX:oY)) ) continue;
        if( (i & 1) == 0 && ++w.no > w.n ) continue;
        w.o = (i & 1)
            ? (w.o & ~(oX|oY)) >> 1
            : (w.o << 1) | ( (i==0)?oX:oY );
        w.s = (w.s << 2) | i;
        if( --w.rem != 0 ) gen( &w );
        else { cnt++; /* output OR check can go here */ return; }
    }
}

FWIW: Here are some pleasing time-trials on my system.
Note: these times include validating that each successive "finished" string is generated in ascending sequence. Spot tests indicate faster times (~70% of these values) are achievable with this code.

N = 5, count = 1344    Elapsed: 0.000 seconds
N = 6, count = 8448    Elapsed: 0.005 seconds
N = 7, count = 54912   Elapsed: 0.030 seconds
N = 8, count = 366080  Elapsed: 0.205 seconds
N = 9, count = 2489344 Elapsed: 1.429 seconds
\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.