Shuffle list except for certain sequences

Question

I want to shuffle an ArrayList but based on some custom conditions: if my array list was something like [1, 4, 5, 6, 9, 45, 67], I want to shuffle it but make sure 5, 6, 9 always appear together.

Is there any method available in Collections class to do this?

I have tried doing this, but it throws ConcurrentModificationException

 List<Integer> y= new ArrayList<>();
 y.add(1);
 y.add(4);
 y.add(5);
 y.add(6);
 y.add(9);
 y.add(45);
 y.add(67);
 List<Integer> z = y.subList(2, 5);
 y.removeAll(z);
 Collections.shuffle(y);
 int index = ThreadLocalRandom.current()
                              .nextInt(0, y.size() + 1);
 y.addAll(index,z);

Answer 1

Without seeing your code, I'd think that the ConcurrentModificationExceptions are thrown because you try to remove the group elements from the list or to add them back in while iterating it. Changing a collection while iterating it leads to those exceptions: Iterating through a Collection, avoiding ConcurrentModificationException when removing in loop.

It will get a lot easier if you do not treat the groups as the exception, but as the norm. What I mean by this is that you should convert your List<?> into a List<List<?>> where each sub list contains either one element or one of the groups. You can then shuffle that list easily with Collections.shuffle() and flatten it again.

Look at this rough implementation:

List<Integer> ints = new ArrayList<>(asList(2, 3, 5, 4, 8, 7, 11, 55));
List<List<Integer>> groups = asList(asList(5, 4), asList(7, 11));

// remove all the grouped elements from the list
groups.forEach(ints::removeAll);

// wrap the single elements into list and join them with the groups
List<List<Integer>> wrapped = Stream.concat(ints.stream().map(Arrays::asList),
                                            groups.stream())
                                    .collect(Collectors.toList());

Collections.shuffle(wrapped);

// flatten the list into single elements again
List<Integer> shuffled = wrapped.stream()
                                .flatMap(Collection::stream)
                                .collect(Collectors.toList());

System.out.println(shuffled); // e.g. [55, 3, 7, 11, 2, 8, 5, 4]
                              //              -----        ----

Note that while this is quite readable, it is probably not the most efficient or error proof solution. But it should give you an idea how to tackle the problem.

---

Edit after comment from Gonen I. Here is a helper method to only remove the exact sequences and not random parts of them all over the list:

private static <T> void removeSequence(List<T> list, List<T> sequence)
{
    int indexOfSubList = Collections.lastIndexOfSubList(list, sequence);
    while (indexOfSubList != -1)
    {
        for (int j = 0; j < sequence.size(); j++)
        {
            list.remove(indexOfSubList);
        }
        indexOfSubList = Collections.lastIndexOfSubList(list, sequence);
    }
}

Use it by replacing groups.forEach(ints::removeAll); by groups.forEach(group -> removeSequence(ints, group));

Answer 2

It sounds like your data should really be a list of lists, especially since its likely that you will have more than 1 group that needs to stay together. You can always flatten it when you need.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class Example {
    public static void main(String[] args) {
        List<List<Integer>> y = new ArrayList<List<Integer>>();
        y.add(new ArrayList<Integer>(Arrays.asList(1)));
        y.add(new ArrayList<Integer>(Arrays.asList(4)));
        y.add(new ArrayList<Integer>(Arrays.asList(5, 6, 9)));
        y.add(new ArrayList<Integer>(Arrays.asList(45)));
        y.add(new ArrayList<Integer>(Arrays.asList(67)));
        Collections.shuffle(y);
        List<Integer> flatList = new ArrayList<>();
        y.forEach(flatList::addAll);

    }

}

Answer 3

A simple way of doing this is to store your target elements in a separate List:

List<Integer> target = new ArrayList<>();
target.add(5);
target.add(6);
target.add(9);

Then shuffle your main list:

Collections.shuffle(y);

Then get a random number from 0 -> y.size().

Random ran = new Random();
int pos = ran.nextInt(y.size());

And insert your target list into your original list:

y.addAll(pos, target);

^{Note: this assumes your original list has the target 3 numbers removed already.}