java - Getting permutations of an int[] removing duplicates sets

Question

I have an array of integers 1<=N<=100, How can I get permutations of this array? Array may contain duplicates, so resulting set of permutations can be duplicate, so need to get all non-duplicate permutations.

• I've found lot of snippets which would convert the int[] to string and perform permutations and printout, but as I hv here is integers of range 1<=N<=100, so converting them into string would spoil integer.
• I can get all permutations with duplicates including, for final set of permutations where duplicates are removed have to check with each other to remove a duplicate or so, it so heavy process.

Is there any simpler way?

For example, 123 would give:

231
321
312
132
213
123

Similarly for 112 program would give:

121
211
211
121
112
112

So, for n-set of elements, permutations will be of n! With duplicates in elements, would decrease tht. I'm asking how can I remove those duplicate sets. (duplicate set of permutation arr[])

Answer 1

If it is acceptable to first sort the elements lexically, then you can your lexical permutation. Including an algorithm which does it for an array of int, easily modifiable to strings.

public static boolean permuteLexically(int[] data) {
    int k = data.length - 2;
    while (data[k] >= data[k + 1]) {
        k--;
        if (k < 0) {
            return false;
        }
    }
    int l = data.length - 1;
    while (data[k] >= data[l]) {
        l--;
    }
    swap(data, k, l);
    int length = data.length - (k + 1);
    for (int i = 0; i < length / 2; i++) {
        swap(data, k + 1 + i, data.length - i - 1);
    }
    return true;
}

Example of how to use it

public static void main(String[] args) {
    int[] data = { 1,2,3 };
    do {
        System.err.println(Arrays.toString(data));
    } while(Util.permuteLexically(data));
}

Using this with [1,2,3] you get

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

with [1,1,3] you instead get

[1, 1, 3]
[1, 3, 1]
[3, 1, 1]

which is what you asked for I think.

Since the method retunes the "next" permutation in lexicographically order it is important that the elements are ordered. Starting with [3, 2, 1] you get no more permutations (compare to example above).