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

possible duplicate of [Permutation of array](http://stackoverflow.com/questions/2920315/permutation-of-array) — RealSkeptic, Jul 07 '15 at 20:02
@Anteaters, the question linked provides a java answer aswell — WorldSEnder, Jul 07 '15 at 20:08
@WorldSEnder That is true, but it prints it, and doesn't put it in an array — Anteaters, Jul 07 '15 at 20:16
@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. — WorldSEnder, Jul 07 '15 at 20:20
Code written in another language can for the most part be easily read through and implemented in another language. — austin wernli, Jul 07 '15 at 21:10

scottb · Answer 1 · 2015-07-07T21:16:58.950

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.

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! ;) — hungryghost, Jul 07 '15 at 21:13

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

1 Answers1