Permutation and sorting of Strings (parentheses problem similarity)

Question

This algorithm runs in \$O(n!)\$ time and I wish I could make this a bit faster for larger elements.

Is there a better approach to solving the parentheses problem in shorter time?

import java.util.ArrayList;
import java.util.Scanner;
public class Main {
 private static ArrayList<String> pathPermutations = new ArrayList<String>();
 private static ArrayList<String> acceptedPathPermutations = new ArrayList<String>();
 private static int numToEnter, mRankingDesired;
 public static void main(String[] args) {
 Scanner myScanner = new Scanner(System.in);
 System.out.println("Enter a node and a desired ranking M: ");
 numToEnter = myScanner.nextInt();
 mRankingDesired = myScanner.nextInt();
 //subtract one from the desired ranking to align rankings up with actual ArrayList indices correctly.
 mRankingDesired--;
 numToEnter--;
 //Calculate all permutations of possible "run" paths.
 calculatePermutations(numToEnter);
 //Check for error since ranking is automatically sorted.
 if (mRankingDesired < acceptedPathPermutations.size() && mRankingDesired >= 0) {
 System.out.println(acceptedPathPermutations.get(mRankingDesired));
 } else {
 System.out.println("ERROR");
 }
 }
 public static void calculatePermutations(int nodeNum) {
 pathPermutations.clear();
 pathPermutations.add(calculateFirstPath(nodeNum));
 createAllPathPermutations(pathPermutations.get(0));
 }
 //
 public static String calculateFirstPath(int nodeNum) {
 //Subtract one from nodeNum to calculate all inner permutations.
 nodeNum--;
 String pathString = "";
 for (int i = 0; i < nodeNum * 2; i++) {
 if (i < nodeNum) {
 pathString += "E";
 } else {
 pathString += "S";
 }
 }
 //nodeNum++;
 return pathString;
 }
 public static void createAllPathPermutations(String initialPath) {
 permutation(initialPath);
 /* for(int i = 0; i<pathPermutations.size()-1;i++){
 System.out.println("PERMUTATION: " + pathPermutations.get(i));
 }
*/
 appendCharacters();
 }
 public static void permutation(String str) {
 permutePath("", str);
 }
 //Calculate unique permutations.
 public static void permutePath(String beginningString, String endingString) {
 if (endingString.length() <= 1) {
 System.out.println(beginningString + endingString);
 if (!pathPermutations.contains(beginningString + endingString)) {
 System.out.println("Adding");
 pathPermutations.add(beginningString + endingString);
 }
 } else {
 for (int i = 0; i < endingString.length(); i++) {
 try {
 String newString = endingString.substring(0, i) + endingString.substring(i + 1);
 permutePath(beginningString + endingString.charAt(i), newString);
 } catch (StringIndexOutOfBoundsException exception) {
 exception.printStackTrace();
 }
 }
 }
 }
 /**
 * Re-append the beginning E and ending S to the list of paths we have calculated.
 */
 public static void appendCharacters() {
 for (int i = 0; i < pathPermutations.size(); i++) {
 String replacement = "E" + pathPermutations.get(i) + "S";
 pathPermutations.set(i, replacement);
 System.out.println(pathPermutations.get(i));
 }
 removeInvalidPaths();
 }
 public static void removeInvalidPaths() {
 for (int i = 0; i < pathPermutations.size(); i++) {
 if (checkPathValidity(pathPermutations.get(i))) {
 acceptedPathPermutations.add(pathPermutations.get(i));
 }
 }
 pathPermutations.clear();
 printOutAcceptedPaths();
 }
 public static boolean checkPathValidity(String pathToCheck) {
 char[] pathToCheckCharArray = pathToCheck.toCharArray();
 int accumulator = 0;
 for (int i = 0; i < pathToCheckCharArray.length; i++) {
 if (pathToCheckCharArray[i] == 'E') {
 accumulator++;
 } else {
 accumulator--;
 if (accumulator < 0) {
 return false;
 }
 }
 }
 return true;
 }
 public static void printOutAcceptedPaths() {
 int numberOfAcceptablePaths = acceptedPathPermutations.size();
 System.out.println("\n Num of Accepted Paths: " + numberOfAcceptablePaths);
 for (int i = 0; i < acceptedPathPermutations.size(); i++) {
 System.out.println("Accepted Path: " + acceptedPathPermutations.get(i));
 }
 }
}

• 200_success: Could you add a brief explanation of what task this code aims to accomplish?
• Timothy Frisch: Certainly it is targeted to solving this problem:
• Timothy Frisch: poj.org/problem?id=3644
• 200_success: If this is code to solve a programming-challenge, please link and summarize the challenge being solve in the question. Otherwise, this question is meaningless, especially if the external site goes away.
• Timothy Frisch: Certainly. I will have to update tomorrow with the problem summary as I am out of town at the moment.

Answer 1

Variables type declaration

private static ArrayList<String> pathPermutations = new ArrayList<String>();
private static ArrayList<String> acceptedPathPermutations = new ArrayList<String>();

It is usually recommended to declare variables by the interface they implement, unless implementation-specific methods are required. Since these two are used simply as Lists, they should be declared as such:

// Assuming Java 7
private static List<String> pathPermutations = new ArrayList<>();
private static List<String> acceptedPathPermutations = new ArrayList<>();

try-with-resources

If you are on Java 7, you can use try-with-resources on the Scanner object for efficient handling of the underlying I/O resource.

try (Scanner myScanner = new Scanner(System.in)) {
 // ...
}

Getting inputs

numToEnter = myScanner.nextInt();
mRankingDesired = myScanner.nextInt();
//subtract one from the desired ranking to align rankings up with actual...
mRankingDesired--;
numToEnter--;

You should just perform the subtraction together with the assignment as such:

// Subtract from input to align rankings with actual list indices.
numToEnter = myScanner.nextInt() - 1;
mRankingDesired = myScanner.nextInt() - 1;

Magic method

//Calculate all permutations of possible "run" paths.
calculatePermutations(numToEnter);

It is not clear how calling the method above also magically initializes acceptedPathPermutations correctly to display the results. Looking at how your method calls are chained, you may want to consider explicitly getting all the permutations in the main() method, then filter them to get your acceptedPathPermutations values:

List<String> pathPermutations = calculatePermutations(numToEnter);
List<String> acceptedPathPermutations = removeInvalidPaths(pathPermutations);

That means abolishing the removeInvalidPaths() call below:

public static void appendCharacters() {
 for (int i = 0; i < pathPermutations.size(); i++) {
 String replacement = "E" + pathPermutations.get(i) + "S";
 pathPermutations.set(i, replacement);
 System.out.println(pathPermutations.get(i));
 }
 // not required
 // removeInvalidPaths();
}

Loop iteration

When you create a for-loop where the iteration value i is used solely for the List.get(int) call, you can use the enhanced for-each loop to achieve the same with lesser code. For example:

public static List<String> removeInvalidPaths(List<String> pathPermutations) {
 List<String> results = new ArrayList<>();
 for (String path : pathPermutations) {
 // consider renaming 'checkPathValidity' as 'isPathValid'
 if (isPathValid(path)) {
 results.add(path);
 }
 }
 // don't think you need the following, they should be done outside the method
 // pathPermutations.clear();
 // printOutAcceptedPaths();
 return results;
}

Java 8

If you happen to be on Java 8, you may want to consider replacing some of the explicit for-loops with Stream-based processing. Using the same removeInvalidPaths as an example:

public static List<String> removeInvalidPaths(List<String> pathPermutations) {
 return pathPermutations.stream().filter(Main::isPathValid)
 .collect(Collectors.toList());
}

This uses the (renamed) isPathValid method reference to filter on the Stream of pathPermutations elements, and then return-ing the collected toList() results to the caller.

Catching Exceptions

Simply using e.printStackTrace() is usually not advised, and this SO question is a good read on this subject. Does your code really not need to handle StringIndexOutOfBoundsException in a more graceful manner?