// Enumerating trees, by Ned Batchelder, Feb 11 2008
// http://nedbatchelder.com/blog/200802/enumerating_trees.html
// Translated to D language by leonardo maffi, V.1.3, Mar 15 2009

import std.stdio: writef, writefln;
import std.string: uppercase;

// My D libs: http://www.fantascienza.net/leonardo/so/libs_d.zip
import d.func: xrange, len, map;
import d.string: joinArray, put, putr;
import d.time: clock;


/********************************************
Generate postfix expressions recursively.
'expr' is the expression so far, a list of values and operators.
'depth' is the depth of the stack created by expr.
'vals' is a list of values remaining to add to the expression.
'ops' is a list of possible operators to choose from.
*/
struct Xexprs {
    string vals, ops, expr;
    int depth;

    int opApply(int delegate(ref string) dg) {
        int result;

        if (depth == 1 && (!vals.length)) {
            // This is a valid expression
            result = dg(expr);
            if (result) goto END;
        }
        if (depth > 1)
            // Try using an operator
            foreach (o; ops)
                foreach (e; Xexprs(vals, ops, expr ~ o, depth-1)) {
                    result = dg(e);
                    if (result) goto END;
                }
        if (vals.length)
            // Vals are available, push one on the stack
            foreach (e; Xexprs(vals[1 .. $], ops, expr ~ vals[0], depth + 1)) {
                result = dg(e);
                if (result) goto END;
            }

        END:
        return result;
    }
}

/********************************************
Concatenate all the strings in words[] together into one
string; use sep[] as the separator.
*/
string[] all_exprs(int n, string ops="+") {
    return map((string e){return joinArray(e, ' ');}, Xexprs(uppercase[0..n], ops));
}

void main() {
    putr(all_exprs(4, "+*").joinArray('\n'), "\n");

    foreach (i; xrange(2, 17)) {
        auto t0 = clock();
        writef("%2d: %9d expressions", i, len(Xexprs(uppercase[0..i], "+")));
        writefln("  %.2f s", clock() - t0);
    }
}


/*

Output (on a Pentium3 at 1/2 GHz):

A B + C + D +
A B + C + D *
A B + C * D +
A B + C * D *
A B + C D + +
A B + C D + *
A B + C D * +
A B + C D * *
A B * C + D +
A B * C + D *
A B * C * D +
A B * C * D *
A B * C D + +
A B * C D + *
A B * C D * +
A B * C D * *
A B C + + D +
A B C + + D *
A B C + * D +
A B C + * D *
A B C + D + +
A B C + D + *
A B C + D * +
A B C + D * *
A B C * + D +
A B C * + D *
A B C * * D +
A B C * * D *
A B C * D + +
A B C * D + *
A B C * D * +
A B C * D * *
A B C D + + +
A B C D + + *
A B C D + * +
A B C D + * *
A B C D * + +
A B C D * + *
A B C D * * +
A B C D * * *

 2:         1 expressions, time: 0.00 s
 3:         2 expressions, time: 0.01 s
 4:         5 expressions, time: 0.01 s
 5:        14 expressions, time: 0.01 s
 6:        42 expressions, time: 0.01 s
 7:       132 expressions, time: 0.01 s
 8:       429 expressions, time: 0.01 s
 9:      1430 expressions, time: 0.02 s
10:      4862 expressions, time: 0.07 s
11:     16796 expressions, time: 0.23 s
12:     58786 expressions, time: 0.82 s
13:    208012 expressions, time: 2.96 s
14:    742900 expressions, time: 10.63 s
15:   2674440 expressions, time: 38.34 s
16:   9694845 expressions, time: 204.18 s
17:  35357670 expressions, time: 656.00 s
18: 129644790 expressions, time: 2181.33 s


Timings on a 2 GHz core 2 CPU:
 2:         1 expressions  0.00 s
 3:         2 expressions  0.00 s
 4:         5 expressions  0.00 s
 5:        14 expressions  0.00 s
 6:        42 expressions  0.00 s
 7:       132 expressions  0.00 s
 8:       429 expressions  0.00 s
 9:      1430 expressions  0.00 s
10:      4862 expressions  0.00 s
11:     16796 expressions  0.03 s
12:     58786 expressions  0.12 s
13:    208012 expressions  0.41 s
14:    742900 expressions  1.55 s
15:   2674440 expressions  5.64 s
16:   9694845 expressions  20.47 s
17:  35357670 expressions  77.68 s

Those are the Catalan numbers.

*/