CODEWITHSUNDEEP
javaduplicatesintegerpermutation
cypronmaya
cypronmaya

Reputation: 520

Getting permutations of an int[] removing duplicates sets

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.

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[])

Upvotes: 3

Views: 8965

Answers (5)

Cris Stringfellow
Cris Stringfellow

Reputation: 3808

You want all non-duplicate permutations of an array. The number of these, assuming each array entry is unique, Factorial(array.length), quickly becomes uncomputably large. But assuming you want to enumerate them the simplest way is to do the following :

Your problem is basically a selection problem over your alphabet (1 <= N <= 100). It does not matter if you want to select 5 of these or 500, you want to select some number, call it, x. Think of the unique elements you want to select from, those that you do not want to duplicate (this may be a proper subset of your alphabet, or not). Lay these elements out in a row. The length of this row is n. Now the selection problem of enumerating a selection of x of these can be solved as follows. Think of an n bit number, that can only ever contain n-x zeroes. To get this rank-x number, simply start from 0 and enumerate all possible numbers up to 2**n, selecting only those that have exactly x 1s (and n-x zeroes). These 1s then select x positions from the n positions of your alphabet, and each of these rank-x numbers selects a permutation for you.

If anyone knows an optimization so that you don't have to work out all the non-rank-x ones, please say so. EDIT: The answer, it seems, is here

Upvotes: 2

Roger Lindsj&#246;
Roger Lindsj&#246;

Reputation: 11543

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).

Upvotes: 6

jenaiz
jenaiz

Reputation: 547

You could use a Set instead of an array of ints, it could delete your duplications automatic.

Edit: @allingeek give me an idea. More than implements your own Set you could write a wrapper over an int and overwrite your equals and hashcode methods, finding the way where your permutations are equals. Perhaps using the numbers in order and others advise given in "Effective Java" (for equals and hashcode implementations to avoid mistakes). It could give you a better way to find your permutations in the Set. More than use expressions language as I say at first.

Upvotes: 3

allingeek
allingeek

Reputation: 1388

  1. Sort the array.
  2. Use a nested loop where the outer loop iterates through each element in the array. If the next element has the same value as the last, skip. The inner loop then places that element at each position in the list. Saving a permutation on each loop.

This will generate the permutations as well as skip repetitious permutations.

int[] sortedSourceArray = ...;
int last = -1;
int current = -1;
// build one permutation with the original array
buildPermutation(permutationList, sortedSourceArray);  // I'm not going to implement this for you.
for (int i = 0; i < sortedSourceArray.length; i++) {
  current = sortedSourceArray[i];
  // check if the new value is the same as the last
  if(current == last) 
    continue;
  // remove the current element from the list
  // build your permutations
  for(int j = 0; j < sortedSourceArray.length; j++) {
    // skip if its inserting the element at its original position
    if(j == i)
      continue;
    // fix the duplicates for blocks of repeated elements
    if(j < sortedSourceArray.length-1 && sortedSourceArray[j+1] == current)
      continue;
    // inject the current element at the new position
    inject(sortedSourceArray, current, j); 
    // build the permutation
    buildPermutation(permutationList, sortedSourceArray);
    // remove the current element from that position
    remove(sortedSourceArray, j);
  }
  last = current;
}

EDIT: Actually I think this would need to be tweaked a bit more to capture the last few cases where duplicates are generated. That would be where a repeated element is inserted next to its same value. I've changed the code appropriately.

Upvotes: 1

Lion
Lion

Reputation: 19027

The easiest method to remove duplicate elements is to add the contents to a Set which won't allow duplicates and then add the Set back to an ArrayList as an example below.

ArrayList<String>al=new ArrayList<String>();

al.add(String.valueOf(arr[0]));  //Just as an example.

HashSet hs = new HashSet();
hs.addAll(al);
al.clear();
al.addAll(hs);

Upvotes: 1

Related Questions