How to generate arrays with some very specific constraints

Question

I want to print 100 int arrays according to some specific constraints.

each array can have a variable length from 2 to 10.
every item in each array must be unique
items in each array are sorted from the lowest to the highest
there are no identical arrays, meaning two arrays having same lenght and same items

At the moment I have this code

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.concurrent.ThreadLocalRandom;

public class prova {
    public static void main(String[] args) {
        Integer[] elements = new Integer[]{1,2,3,4,5,6,7,8,9,10};

        Set<List<Integer>> seenAlready = new HashSet<>();


        for (int i = 0; i < 100; i++) {
            final Integer[] array = generateRandomArrayFromElements(elements);
            Arrays.sort(array);


            if (seenAlready.add(Arrays.asList(array)))
                System.out.println(Arrays.toString(array));

        }
    }

    private static Integer[] generateRandomArrayFromElements(Integer[] elements) {
        int size = ThreadLocalRandom.current().nextInt(1, elements.length) + 1;
        Integer[] array = new Integer[size];
        ArrayList<Integer> usedIndices = new ArrayList<>(size);
        for (int i = 0; i < array.length; i++) {
            int randomIndex = getUniqueRandomIndex(usedIndices, size);
            usedIndices.add(randomIndex);
            array[i] = elements[randomIndex];
        }
        return array;
    }

    private static int getUniqueRandomIndex(ArrayList<Integer> usedIndices, int max) {
        int randomIndex = ThreadLocalRandom.current().nextInt(0, max);
        final boolean contains = usedIndices.contains(randomIndex);
        if (contains)
            randomIndex = getUniqueRandomIndex(usedIndices, max);
        return randomIndex;
    }
}

The problem is that it just generates arrays too similar too each other.

They all look the same!

Have a look at one of its possible outputs:

[1, 2, 3, 4, 5, 6] 
[1, 2, 3, 4, 5, 6, 7, 8] 
[1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 2, 3, 4, 5]
[1, 2, 3]
[1, 2, 3, 4] 
[1, 2, 3, 4, 5, 6, 7] 
[1, 2] 
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

I'm never getting arrays like:

[3,4,8,9]
[2,3,6,7,8]

Everytime they start with [1,2,3,4] and so on!

I don't get it!

Seems like it could be a bug: http://stackoverflow.com/a/7139555/1366973 What version of the JDK are you using? — MrHappyAsthma, Dec 22 '16 at 17:36
Checking with java -version command in Windows command propmpt I get 1.8.0_111 — NoobNe0, Dec 22 '16 at 17:41

Rafał Spryszyński · Accepted Answer · 2016-12-22T18:01:34.960

The problem is that You are generating index in range from 0 to array.length.

So if the array size is 2, then Your range is <0,2)
If the array size is 3, then Your range is <0,3)
...
If the array size is 10, then Your range is <0,10)

And in that situation there is no way to generate different results than You showed us.

Spots to fill  |Elements to choose from based on range
=======================================
[_,_]          |[1,2,................] range <0,2)
[_,_,_]        |[1,2,3,..............] range <0,3)
[_,_,_,_]      |[1,2,3,4,............] range <0,4)
...

You should invoke it like this int randomIndex = getUniqueRandomIndex(usedIndices, elements.length);

Notice that max changed to elements.length.

Your example with the item representation made the explanation immediately clear. I know see where the problem is. Thanks a lot. — NoobNe0, Dec 22 '16 at 18:12

score 0 · Answer 2 · answered Dec 22 '16 at 17:35

1 - Start to generate 100 empty arrays with a variable length from 2 to 10.

2 - Count the total size.

3 - Generate x uniques integers and add them to a Set.

Set<Integer> set = new HashSet<Integer>();
    while(set.size()< xxx) {
        set.add(generateRandomInteger());
    }

    Collections.sort(set);

(where xxx is the total array size

4 - add the integers into your arrays.

How to generate arrays with some very specific constraints

2 Answers2