Randomizing set of duplicate arrays in Java without repeating elements

Question

In my problem I have few arrays with numbers 1 - 3,

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

I combined the arrays into one full array,

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

I need to randomize the array each run, so that no element repeats.

For example, this would work

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

but this would not.

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

I chose 1,2,3 to simplify it, but my arrays would consist of the numbers 1 - 6. The idea remains the same though. Is there an algorithm or easy method to accomplish this?

Answer 1

This is a heuristic solution for random shuffling not allowing consecutive duplicates. It applies to lists, but it's easy to transfer it to arrays as it does only swapping and no shift operations are required. It seems to work in the majority of cases for lists consisting of millions of elements and various density factors, but always keep in mind that heuristic algorithms may never find a solution. It uses logic from genetic algorithms, with the exception that this version utilizes one individual and selective mutation only (it's easy to convert it to a real genetic algorithm though), but it's simple and works as follows:

If a duplicate is found, try swapping it with a random element after it; if not possible, try swapping it with an element prior to it (or vice versa). The key point here is the random position for exchanging elements, so as to keep a better uniform distribution on random output.

This question has been asked in alternative forms, but I couldn't find an acceptable solution yet. Unfortunately, as most of the proposed answers (except for the "greedy" extensive re-shuffling till we get a match or computing every combination), this solution does not provide a perfect uniform distribution, but seems to minimize some patterns, :( still not possible to remove every pattern, as you see below. Try it and post any comments for potential improvements.

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Random;

//Heuristic Non-Consecutive Duplicate (NCD) Shuffler
public class NCDShuffler {

    private static Random random = new Random();
    //private static int swaps = 0;

    public static <T> void shuffle (List<T> list) {
        if (list == null || list.size() <= 1) return;
        int MAX_RETRIES = 10; //it's heuristic
        boolean found;
        int retries = 1;
        do {
            Collections.shuffle(list);
            found = true;
            for (int i = 0; i < list.size() - 1; i++) {
                T cur = list.get(i);
                T next  = list.get(i + 1);
                if (cur.equals(next)) {

                    //choose between front and back with some probability based on the size of sublists
                    int r = random.nextInt(list.size());
                    if ( i < r) {
                        if (!swapFront(i + 1, next, list, true)) {
                            found = false;
                            break;
                        }
                    } else {
                        if (!swapBack(i + 1, next, list, true)) {
                            found = false;
                            break;
                        }
                    }
                }
            }
            retries++;
        } while (retries <= MAX_RETRIES && !found);

    }

    //try to swap it with an element in a random position after it
    private static <T> boolean swapFront(int index, T t, List<T> list, boolean first) {
        if (index == list.size() - 1) return first ? swapBack(index, t, list, false) : false;
        int n = list.size() - index - 1;
        int r = random.nextInt(n) + index + 1;
        int counter = 0;
        while (counter < n) {
            T t2 = list.get(r);
            if (!t.equals(t2)) {
                Collections.swap(list, index, r);
                //swaps++;
                return true;
            }
            r++;
            if (r == list.size()) r = index + 1;
            counter++;
        }

        //can't move it front, try back
        return first ? swapBack(index, t, list, false) : false;
    }

    //try to swap it with an element in a random "previous" position
    private static <T> boolean swapBack(int index, T t, List<T> list, boolean first) {
        if (index <= 1) return first ? swapFront(index, t, list, false) : false;
        int n = index - 1;
        int r = random.nextInt(n);
        int counter = 0;
        while (counter < n) {
            T t2 = list.get(r);
            if (!t.equals(t2) && !hasEqualNeighbours(r, t, list)) {
                Collections.swap(list, index, r);
                //swaps++;
                return true;
            }
            r++;
            if (r == index) r = 0;
            counter++;
        }
        return first ? swapFront(index, t, list, false) : false;
    }

    //check if an element t can fit in position i
    public static <T> boolean hasEqualNeighbours(int i, T t, List<T> list) {
        if (list.size() == 1) 
            return false;
        else if (i == 0) {
            if (t.equals(list.get(i + 1)))
                return true;
            return false;
        } else {
            if (t.equals(list.get(i - 1)) || (t.equals(list.get(i + 1))))
                return true;
            return false;
        }
    }

    //check if shuffled with no consecutive duplicates
    public static <T> boolean isShuffledOK(List<T> list) {
        for (int i = 1; i < list.size(); i++) {
            if (list.get(i).equals(list.get(i - 1)))
                return false;
        }
        return true;
    }
    //count consecutive duplicates, the smaller the better; We need ZERO
    public static <T> int getFitness(List<T> list) {
        int sum = 0;
        for (int i = 1; i < list.size(); i++) {
            if (list.get(i).equals(list.get(i - 1)))
                sum++;
        }
        return sum;
    }

    //let's test it
    public static void main (String args[]) {
        HashMap<Integer, Integer> freq = new HashMap<Integer, Integer>();
        //initialise a list
        List<Integer> list = new ArrayList<Integer>();
        list.add(1);
        list.add(1);
        list.add(2);
        list.add(3);

        /*for (int i = 0; i<100000; i++) {
            list.add(random.nextInt(10));
        }*/

        //Try to put each output in the frequency Map
        //then check if it's a uniform distribution
        Integer hash;
        for (int i = 0; i < 10000; i++) {
            //shuffle it
            shuffle(list);

            hash = hash(list);
            if (freq.containsKey(hash)) {
                freq.put(hash, freq.get(hash) + 1);
            } else {
                freq.put(hash, 1);
            }
        }
        System.out.println("Unique Outputs: " + freq.size());
        System.out.println("EntrySet: " + freq.entrySet());
        //System.out.println("Swaps: " + swaps);
        //for the last shuffle
        System.out.println("Shuffled OK: " + isShuffledOK(list));
        System.out.println("Consecutive Duplicates: " + getFitness(list));
    }

    //test hash
    public static int hash (List<Integer> list) {
        int h = 0;
        for (int i = 0; (i < list.size() && i < 9); i++) {
            h += list.get(i) * (int)Math.pow(10, i); //it's reversed, but OK
        }
        return h;
    }
}

This is a sample output; it's easy to understand the issue with the non-uniform distribution.

Unique Outputs: 6

EntrySet: [1312=1867, 3121=1753, 2131=1877, 1321=1365, 1213=1793, 1231=1345]

Shuffled OK: true

Consecutive Duplicates: 0

Answer 2

The most optimal solution, I can think of, is to count the number of occurrences of each value, logically creating a "pool" for each distinct value.

You then randomly choose a value from any of the pools that are not the value of the previous selection. The random selection is weighted by pool sizes.

If a pool is more than half the size of all remaining values, then you must choose from that pool, in order to prevent repetition at the end.

This way you can produce result fast without any form of retry or backtracking.

Example (using letters as values to clarify difference from counts):

Input: A, B, C, A, B, C

Action                              Selected     Pools(Count)
                                               A(2)  B(2)  C(2)
Random from all 3 pools                A       A(1)  B(2)  C(2)
Random from B+C pools                  C       A(1)  B(2)  C(1)
Random from A+B pools (1:2 ratio)      A       A(0)  B(2)  C(1)
Must choose B (>half)                  B       A(0)  B(1)  C(1)
Random from A+C, so C                  C       A(0)  B(1)  C(0)
Must choose B (>half)                  B       A(0)  B(0)  C(0)

Result: A, C, A, B, C, B

Answer 3

There's no pre-written algorithm that I know of (which doesn't mean one doesn't exist), but the problem is easy to understand and the implementation is straightforward.

I will offer two suggestions dependent on if you want to build a valid array or if you want to build an array and then check its validity.

1 - Create some collection (Array, ArrayList, etc) that contains all of the possible values that will be included in your final array. Grab one of those values and add it to the array. Store a copy of that value in a variable. Grab another value from the possible values, check that it's not equal to your previous value, and add it to the array if it's valid.

2 - Create an array that contains the number of values you want. Check that item n != item n+1 for all items except the last one. If you fail one of those checks, either generate a new random value for that location or add or subtract some constant from the value at that location. Once you have checked all of the values in this array, you know you have a valid array. Assuming the first and last values can be the same.

Answer 4

If the arrays are relatively small, it would not be too hard for you just to combine the two arrays, randomize it then check the numbers, and if there are too same numbers just shift one over or just randomize it again.

Answer 5

You could use Collections.shuffle to randomize the list. Do it in a while loop, until the list passes your constraint.