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

Answer 1

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.

Answer 2

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)); }

Answer 3

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];
    }
}