public class PrintPermutations{
Classes are types of things, so they usually get noun names, e.g.
public class PermutationPrinter<T> {
You mention that you want this to work with generic types. The way to do that is to add a generic parameter.
public void printPermutations(String prefix,int[] arr){
Unfortunately, there are no generic arrays in Java, so you have to switch to a different data type. You have a list of items, so let's switch to List
.
public void permuteAndPrint(String prefix, List<T> items) {
Your method actually does two things, not one. Thus, the compound name. This actually violates something called the Single Responsibility Principle, but I'm going to ignore that for now.
I prefer plural names for collections, so I changed the now inaccurate arr
to items
.
Side note: you use eight column indent for the first two levels and then use smaller indents thereafter. The usual suggestion is to always tab the same amount. I switched to a consistent four column tab, as that's pretty common (standard) in Java programming.
if(arr.length == 1){
System.out.println(prefix + arr[0]);
}else{
Rather than use an if
/else
construct, it is common to return from the base case of a recursive function:
if (items.size() == 1) {
System.out.println(prefix + items.get(0));
return;
}
This allows the rest of the function to work without extra indent and makes it more recognizable as a base case.
for(int i=0;i<arr.length;i++){
printPermutations(prefix+arr[i]+",",taperedArray(arr,i));
}
There are several things that I don't like about this, starting with the index-based for
loop. I'd rather use the foreach format:
for ( T item : items ) {
List<T> remnants = new ArrayList<T>(items);
remnants.remove(item);
permuteAndPrint(prefix + item + ",", remnants);
}
A useful feature of List
is that it includes a remove
function that replaces your taperedArray
function.
Now rather than saying arr[i]
, we can say a more readable item
.
So the whole class is now
public class PermutationPrinter<T> {
public void permuteAndPrint(String prefix, List<T> items) {
if (items.size() == 1) {
System.out.println(prefix + items.get(0));
return;
}
for ( T item : items ) {
List<T> remnants = new ArrayList<T>(items);
remnants.remove(item);
permuteAndPrint(prefix + item + ",", remnants);
}
}
public static void main(String[] args) {
PermutationPrinter<Integer> printer = new PermutationPrinter<Integer>();
List<Integer> data = Arrays.asList(1,2,3);
printer.permuteAndPrint("", data);
}
}
This does mostly the same steps as your original and still violates the Single Responsibility Principle. Normally we'd write main
something like
public static void main(String[] args) {
List<Integer> data = Arrays.asList(1,2,3);
PermutationPrinter<Integer> printer = new PermutationPrinter<Integer>(data);
printer.permute();
printer.print();
}
This has several advantages. For one, it saves the caller from passing an empty string to the recursive function. Instead, we can now write
public class PermutationPrinter<T> {
List<T> items;
List<List<T>> permutations = new ArrayList<>();
public PermutationPrinter(List<T> data) {
items = data;
}
private void _permute(List<T> permutation, List<T> data) {
if (data.size() <= 0) {
permutations.add(permutation);
return;
}
for ( T datum : data ) {
List<T> remnants = new ArrayList<T>(data);
remnants.remove(datum);
List<T> elements = new ArrayList<T>(permutation);
elements.add(datum);
_permute(elements, remnants);
}
}
private void permute() {
List<T> permutation = new ArrayList<T>();
_permute(permutation, items);
}
private void print() {
for ( List<T> permutation : permutations ) {
T last = permutation.remove(permutation.size() - 1);
for ( T element : permutation ) {
System.out.print(element + ", ");
}
System.out.println(last);
}
}
}
Notice how this hides the details of how the recursive function works inside a public method. This allows the recursive method to be private. We could change its interface tomorrow with no impact outside this class.
Another advantage is that it is easier to unit test the state of variables than output. So we may not be able to unit test print
, but we can certainly unit test permute
and _permute
.
This also allows us to move main
out of the class and into its own class. This class shouldn't need a main
method.
Note: I haven't attempted to optimize the algorithm. I just rewrote it in a new style.