1
\$\begingroup\$

This code is a proof-of-concept which I intend to convert into a static utility / helper class. I'm looking at this review from a structure or performance viewpoint. Small detail such as whether it prints or returns something, or whether the output is well-formatted, don't concern me too much.

The purpose of this code sample is:

  • Given an input of an arbitrary set of strings, such as A B C, return all the sets of permutations or combinations of these, where each is used only once; in this example, it would return (or print) the following 7 sets:
    • ABC (Use all 3)
    • AB, BC, AC (Combinations of pairs)
    • A, B, C (Each item individually)
  • The sequence of each doesn't matter (They happen to be alphabetical in the output)
  • If we have AB we don't also need BA (These can be permutated later by such libraries as Guava's Collections2.permutations()

import java.util.Arrays;
import java.util.Set;
import java.util.TreeSet;

public class PermutationTest {

  private String[] strings;
  private int t;
  private int[] i;
  private Set<String> unique = new TreeSet<>();

  private PermutationTest(int t, String... strings) {
    this.strings = strings;
    this.t = t;
    this.i = new int[t];
    for(int x = 0 ; x < this.t ; x++ ) {
      i[x] = x;
    }
  }

  private boolean permutate() {
    return permutate(this.t - 1);
  }

  private boolean permutate(int c) {
    if(c < 0) {
      return false;
    }
    this.i[c]++;
    int m = this.strings.length - (this.t - c - 1);
    if(this.i[c] >= m) {
      if(permutate(c - 1)) {
        this.i[c] = this.i[c - 1] + 1;
      } else {
        return false;
      }
    }
    return true;
  }

  private void print() {
    System.out.println(Arrays.toString(this.i));
    StringBuilder sb = new StringBuilder();
    for(int x = 0 ; x < this.t ; x++ ) {
      sb.append(this.strings[i[x]]);
    }
    this.unique.add(sb.toString());
  }

  public static void main(String[] args) {
    String[] strings = (args.length > 0) ? args : new String[] {"A", "B", "C"};
    Set<String> total = new TreeSet<>();
    for(int z = 0 ; z < strings.length ; z++ ) {
      total.addAll(outer(z + 1, strings));
    }
    System.out.println(total.size());
    System.out.println(total);
  }

  private static Set<String> outer(int z, String[] strings) {
    PermutationTest p = new PermutationTest(z, strings);
    int c = 0;
    boolean running = true;
    while(running && c < 200) {
      p.print();
      running = p.permutate();
      c++;
    }
    System.out.println(String.format("Total %d permutation count", c));
    System.out.println(String.format("Total %d unique strings", p.unique.size()));
    System.out.println(p.unique);
    return p.unique;
  }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Just as an initial consideration, the code could use some comments and/or a more descriptive naming convention for variables. \$\endgroup\$ – gcali May 16 '16 at 12:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.