Permuting large list of elements in array in java

Question

Hello I have list of 1000 elements with duplicates and if I want to get all the permutations of the them after removing the duplicates then what would be the best and most mathematically efficient way of doing so.

Random rand = new Random();
for (int i = 0 ; i < 1000 ; i ++) {
        list.add(i,rand.nextInt(500));
}

With above we get an array of 1000 elements and there will be duplicate elements too. What is a better way to print the permutations so that it consumes less memory space and less time.

I have worked with the Recursive Permutation algorithm but it takes time for values of n > 15 and also after a point an exception is thrown heap memory overflow.

Will something this be better, http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

Add all your list items to a `Set` - that will remove the duplicates, see [Removing duplicate elements from a List](http://stackoverflow.com/questions/10370750/removing-duplicate-elements-from-a-list). Not sure why you haven't already found this with your prior research... — Duncan Jones, May 12 '14 at 15:50
if you want to list all permutation no algorithm can work better than n! — coder hacker, May 12 '14 at 15:51

score 0 · Answer 1 · answered May 12 '14 at 15:55

0

The java.util.Set class automatically purges duplicates.

Set set = new HashSet<>(); Random rand = new Random(); for (int i = 0 ; i < 5000 ; i ++) { set.add(i,rand.nextInt(100)); }

answered May 12 '14 at 15:55

DirkyJerky

1,130
5
10

I know how to take care of the duplicates. `new ArrayList(new LinkedHashSet(Arrays.asList(array)));` where array is the String list – user3588346 May 12 '14 at 15:59

score 0 · Accepted Answer · answered May 12 '14 at 15:59

0

First, generating all permutations takes time. It takes so much time that permuting your 5000 elements would take more time than the estimate age of our universe.

Second, storing all the permutations is inefficient. Instead, you want to generate the permutations on the fly. Take a look at this code : http://cs.fit.edu/~ryan/java/programs/combinations/Permute-java.html.

answered May 12 '14 at 15:59

Danstahr

4,190
22
38

I have edited a few values which I had written wrong but still I think there is no algorithm which provides a better efficiency than O(n!) – user3588346 May 12 '14 at 16:10
Surely there isn't, the size of the output *is* `O(N * N!)`. I've never tried, but I think you can't sanely permute more than say 30 elements. – Danstahr May 12 '14 at 16:12
That's a problem I had whenever I try to get them for larger n I get heap memory error. Well okay. Thanks – user3588346 May 12 '14 at 16:14
The memory issue should be solved using the code provided since it needs just `O(N)` extra memory, not `O(N*N!)`. Unless you store the results somewhere of course. – Danstahr May 12 '14 at 16:16

score 0 · Answer 3 · answered May 12 '14 at 16:39

Inplace permutation. This first sorts the array and find all permutaitons with the array. On each iteration it changes the array as well.

import java.util.Arrays;
import java.util.HashSet;
import java.util.Random;
import java.util.Set;

import org.apache.commons.lang3.ArrayUtils;

public class Permutate {

    public static void main(String[] args) {
        Permutate permutator = new Permutate();
        Set<Integer> data = new HashSet<Integer>();
        Random r = new Random();
        for (int i = 0 ; i < 5000 ; i ++) {
        data.add(r.nextInt(100));
        }
        int[] array = ArrayUtils.toPrimitive(data.toArray(new Integer[data.size()]));
        Arrays.sort(array);
        do{
            System.out.println(Arrays.toString(array));
        } while(permutator.permutate(array) != -1);
    }

    public int permutate(int[] array) {
        int i, j;

        for (i = array.length - 2; i >= 0; i--) {
            if (array[i] < array[i + 1])
                break;
        }
        if (i < 0) {
            return -1;
        }

        for (j = array.length - 1; j > i; j--) {
            if (array[j] > array[i])
                break;
        }

        swap(array, i++, j);

        for (j = array.length - 1; j > i; i++, j--) {
            swap(array, i, j);
        }
        return 0;
    }

    public void swap(int[] array, int x, int y) {
        array[x] ^= array[y];
        array[y] ^= array[x];
        array[x] ^= array[y];
    }
}

Permuting large list of elements in array in java

3 Answers3