Tim1
BAN USERI like algorithms
Naive implementation using recursive invocations.
Idea: consider a generation of a string as being done for a particular number of characters, for example, string for "abc" generate strings with 1 char, 2 chars and 3 chars.
Let's call them levels. A string at a level is formed from a current char + all combinations for the substring starting with the next character at level - 1.
For example, "abc" for level = 2 and char "a" has to be considered a substring "bc" at level = 1 (which are "b" and "c")
import static org.hamcrest.MatcherAssert.assertThat;
import static org.hamcrest.Matchers.arrayContainingInAnyOrder;
import static com.google.common.collect.Sets.newHashSet;
import java.util.Set;
public class PrintPowerSetOfAString {
public static Set<String> superSet(final String s) {
final Set<String> result = newHashSet("");
if (s == null || s.length() == 0) {
return result;
}
/*
* Level is the number of characters + 1 that have to be taken from the string, for example,
* string: "abc"
* level 0: "a", "b", "c"
* level 1: "ab", "ac", "bc"
* level 2: "abc"
*/
for (int lvl = 0; lvl < s.length(); lvl++) {
result.addAll(get(s.toCharArray(), 0, lvl));
}
return result;
}
/**
* Returns combination of strings for a substring starting with {@code start} with number of characters
* {@code lvl + 1}.
*/
public static Set<String> get(final char[] a, final int start, final int lvl) {
final Set<String> result = newHashSet();
if (start >= a.length) {
return result;
}
if (lvl < 0) {
return result;
}
for (int i = start; i < a.length; i++) {
// get combinations of the substring starting from the next char with lvl number of chars
Set<String> set = get(a, i + 1, lvl - 1);
if (!set.isEmpty()) {
for (String s : set) {
result.add(a[i] + s);
}
} else {
if (lvl + 1 == 1) {
result.add(String.valueOf(a[i]));
}
}
}
return result;
}
public static void main(final String[] args) {
assertThat("", superSet("a").toArray(new String[0]), arrayContainingInAnyOrder("", "a"));
assertThat("", superSet("abc").toArray(new String[0]),
arrayContainingInAnyOrder("", "a", "b", "c", "ab", "ac", "bc", "abc"));
assertThat("", superSet("abcde").toArray(new String[0]),
arrayContainingInAnyOrder("", "a", "b", "c", "d", "e", "ab", "ac", "ad", "ae", "bc", "bd", "be", "cd", "ce",
"de", "abc", "abd", "abe", "acd", "ace", "ade", "bcd", "bce", "bde", "cde", "abcd", "abce", "abde",
"acde", "bcde", "abcde"));
}
}
Idea is based on qsort-partitioning where order of elements is preserved and done *in place*.
As input function takes 2 arrays, applies partitioning on them and recursively processes each of 2 sub arrays.
public class CompareArraysAsBST {
public static boolean areBSTEqual(final int[] a, final int[] b) {
if (a == null || b == null) {
return false;
}
return areBSTEqual(a, 0, a.length - 1, b, 0, b.length - 1);
}
/**
* Returns true if 2 arrays are BST equal from index start to index end inclusive.
*/
private static boolean areBSTEqual(final int[] firstArr, final int firstStart, final int firstEnd,
final int[] secondArr, final int secondStart, final int secondEnd) {
// indexes have to be always the same for both arrays
if (firstStart != secondStart || firstEnd != secondEnd) {
return false;
}
// if we are outside of the array then ok
if (firstStart >= firstArr.length && secondStart >= secondArr.length) {
return true;
}
//if first indexes are bigger than end ones return true
if (firstStart > firstEnd || secondStart > secondEnd) {
return true;
}
// if first elements of the array are not the same then arrays are not BST same
if (firstArr[firstStart] != secondArr[secondStart]) {
return false;
}
int firstBorder = partition(firstArr, firstStart, firstEnd);
int secondBorder = partition(secondArr, secondStart, secondEnd);
// recursive invocation on 2 pieces of an array exclusive the first one (we checked it already)
boolean areEqualLeft = areBSTEqual(firstArr, firstStart + 1, firstBorder - 1, secondArr, secondStart + 1,
secondBorder - 1);
boolean areEqualRight = areBSTEqual(firstArr, firstBorder, firstEnd, secondArr, secondBorder, secondEnd);
return areEqualLeft && areEqualRight;
}
/**
* Sorts an array in qsort way but elements' order is presumed.
* Returns an index of the first element that is *bigger* than a[begin]
*/
private static int partition(final int[] a, final int start, final int end) {
// loop invariant: res is always pointing to the first element *bigger* than a[begin]
int res = start + 1;
for (int i = start + 1; i <= end; i++) {
// if found an element that is less than a[begin] then circularly shift the sub array of elements
// example: 4 1 3 5 8 2 7, res = 3 (a[res] = 5), i = 5 (a[i] = 2) -> shift the sub array {5 8 2} -> {2 5 8}
// so that array becomes 4 1 3 2 5 8 7 and res = 6 (a[res] = 5)
if (a[i] <= a[start]) {
swapWithShift(a, res, i);
++res;
}
}
return res;
}
private static void swapWithShift(final int[] a, final int start, final int end) {
int tmp = a[end];
for (int i = start; i <= end; i++) {
int tmp2 = a[i];
a[i] = tmp;
tmp = tmp2;
}
}
public static void main(final String[] args) {
assertThat("", areBSTEqual(new int[] {2, 1, 3}, new int[] {2, 3, 1}), is(true));
assertThat("", areBSTEqual(new int[] {5, 1, 3, 4, 8, 7, 6}, new int[] {5, 8, 1, 3, 7, 6, 4}), is(true));
assertThat("", areBSTEqual(new int[] {3, 2, 3}, new int[] {2, 3, 1}), is(false));
assertThat("", areBSTEqual(new int[] {2, 1, 3, 5}, new int[] {2, 3, 1}), is(false));
assertThat("", areBSTEqual(new int[] {4, 2, 3, 1, 7}, new int[] {4, 2, 1, 3, 7}), is(true));
assertThat("", areBSTEqual(new int[] {}, new int[] {}), is(true));
assertThat("", areBSTEqual(null, null), is(false));
}
}
Very elegant solution + 1, but Math.pow() could be calculated once
- Tim1 June 08, 2013