Java putting all permutations of an Int array into another array without repeats

Question

There are many other questions on Stack Overflow like this, but this one asks for something different than the others. I want to know how to take all permutations of an int array, without repeats, and put them in another 2D array. For example, the input: {1,2,3} the output:

{1,2,3}
{1,3,2}
{2,1,3}
{2,3,1}
{3,1,2}
{3,2,1}

How can I accomplish this? I'd like just a verbal walk through on how to do this, or even better some code. My question differs from this one because the linked one uses C++ functions to accomplish this. I use Java.

Thanks

• Karthik: are there any duplicates in the input?
• Anteaters: @karthik No, there are no
• RealSkeptic: possible duplicate of Permutation of array
• WorldSEnder: @Anteaters, the question linked provides a java answer aswell
• WorldSEnder: @Anteaters, that is an easy change, you shouldn't expect to get all the code chewed for you. I am sure you can adapt the change so that it stores them in a list.

Answer 1

Java is an object-oriented language and so I believe it is useful to consider what objects your problem might contain.

One thing that immediately jumps out of your problem domain is the triple-set of integers, so why not define this as an object:

public class Triad {
 private final int[] components;
 public Triad(int... numbers) {
 this.components = numbers;
 if (components.length != 3) throw new IllegalArgumentException();
 }
 @Override public boolean equals(Object ob) {
 if (ob == this) return true; 
 if (!(ob instanceof Triad)) return false;
 Triad test = (Triad) ob;
 return Arrays.equals(this.components, test.components);
 }
 @Override public int hashCode() {
 return Arrays.hashCode(this.components);
 }
}

Note that Triad defines an equals() method and a hashCode() method. This is important for a couple of reasons. Triad is a value class, i.e. instances of Triad represent values rather than something active. Value classes typically:

• should be immutable (as we have defined Triad so far, it is immutable)
• have well-formed equals() and hashCode() methods

the last property above allows instances to be used without fear with the Java Collections Framework. Now let's put the Collections Framework to use:

public static void main(String[] args) {
 Set<Triad> triads = new HashSet<Triad>();
 Triad inputTriad;
 while (true) {
 int[] numbers = ... // read in data from some source
 if (numbers == null) break;
 inputTriad = new Triad(numbers);
 triads.add(inputTriad);
 }
 // after the loop has completed, the HashSet instance triad will contain
 // all your input triads. The contract of HashSet guarantees that there
 // will be no duplicates.
 :
 :
}

If you must have your result in int arrays, it is now a simple matter to iterate through the HashSet instance and assign the component values of each element to your result arrays.

• hungryghost: Great answer. Up-voted, but my guess is the OP is looking for a way to do this using arrays. The question sounds like a Java homework exercise. Your answer is for next semester's Advanced Java course! ;)