Playing with code

Reading time ~4 minutes

I haven’t been programming algorithms for fun for the last 4, maybe 5 years. At the moment I have realized that it could be a good thing to do… So this is the first try :)

Give you a number N, print all valid combinations of ( and ). e.g.N == 1, then print () N == 2, then print ()(), (()) N == 3, then print ()()(), (())(), ()(()), ((())) N ==.

###The idea: Sequences can be viewed as numbers: 1 : 1 , 2 : 11 2, 3: 111 12 21 3, etc. This has a nice recursive property, for an x we take all the numbers y in [1,x] and append in in front of the solution for (x-y). Except x=1 and 0, which give “1” and “ ” respectively.

A simple solution is as follows:

public class Balls {
	public static String balls(int x) {
		String ret = "";
		for (int i=1; i<=x; i++) ret += "(";
		for (int i=1; i<=x; i++) ret += ")";
		return ret;
	}

	public static String print(String prefix, int x) {
		if (x == 0) {
			return prefix + " ";
		} else if (x == 1) {
			return prefix + "() ";
		} else {
			String ret = "";
			for (int i = 1; i <= x; i++){
				ret += prefix + print(balls(i), x - i);
			}
			return ret;
		}
	}

	public static String print(int x) {
		return print("", x);
	}

	public static void main(String[] args) {
		System.out.println(1 + ":" + print(1));
		System.out.println(2 + ":" + print(2));
		System.out.println(3 + ":" + print(3));
		System.out.println(4 + ":" + print(4));
	}
}

Now, the problem with this solution is recursion and repeated calls to same print(String,int) and balls(int). The running time is O(2^n). A better solution is as follows (perhaps ArrayList can be swaped out with an array):

public static String printDP(int x) {
	ArrayList prints[] = new ArrayList[x + 1];
	if (x == 0) {
		return "";
	} else if (x == 1) {
		return "()";
	}
	prints[0] = new ArrayList();
	prints[0].add("");
	prints[1] = new ArrayList();
	prints[1].add("()");
	String pres[] = new String[x + 1];
	pres[0] = "";
	for (int i = 1;i <= x; i++) {
		pres[i] = "(" + pres[i - 1] + ")";
	}
	for (int i = 2; i <= x; i++) {
		prints[i] = new ArrayList();
		for (int j = 1; j <= i; j++) {
			for (String s : prints[i - j]) {
				prints[i].add(pres[j] + s);
			}
		}
	}
	String ret = "";
	for (String s : prints[x]) {
		ret += s + " ";
	}
	return ret;
}

The running time is O(n^3).

On designing and running online experiments

Have you wondered how to design and run online experiments? In particular, how to implement an experiment dashboard such as the one enpic...… Continue reading

Software Engineering at Cxense

Published on April 17, 2017

Having fun with Scikit-Learn

Published on December 01, 2016