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

doubt it. you are looking for a very specific rule, which sort of goes against all the rest of the elements. Pretty sure the inventors of Java didn't have an "we need to keep 5, 6 and 9 always together" mindset — Stultuske, Feb 14 '18 at 07:46
*"we need to keep 5, 6 and 9 always together" mindset* - LOL — Scary Wombat, Feb 14 '18 at 07:54
thanks for the humor guys, i was expecting help not this. @ThumChoonTat what if i had multiple such groups? — Bhargav, Feb 14 '18 at 08:49
Use another array list to store the groups would do. After shuffle put each group back into the list — Thum Choon Tat, Feb 14 '18 at 08:51
when you say put, i would need to randomize that too, that is where i am having issues — Bhargav, Feb 14 '18 at 08:52
Your code is wrong even if there is no exception thrown. ` y.removeAll(z);` will remove all 5,6,9 even if there are not neighbors. — xingbin, Feb 14 '18 at 09:08
@user6690200: yes i wanted to remove them and shuffle, whats wrong in that? — Bhargav, Feb 14 '18 at 09:26
@Bhargav If your array is `1, 4, 5, 6, 9, 45, 67, 5`, you will lost the end element 5 with `removeAll`. It will not be put back. — xingbin, Feb 14 '18 at 10:04

score 1 · Answer 1 · answered Feb 14 '18 at 09:07

1

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.}

answered Feb 14 '18 at 09:07

achAmháin

4,176
4
17
40

Hi, i have tried the same thing almost. But was wondering what if there are multiple such target groups? – Bhargav Feb 14 '18 at 09:26
Also i get java.util.ConcurrentModificationException at the addAll line – Bhargav Feb 14 '18 at 09:28
thats because you are not doing the "note" part. try doing this then you will get that y.removeAll(z); – Bhargav Feb 14 '18 at 09:35
If you wrap **every** element in its own list, and keep the grouped elements together in the same lists, you end up with a list of lists, which you can shuffle and then flatten again. `List -> groupd & wrap -> List -> shuffle -> flatten -> List` – Malte Hartwig Feb 14 '18 at 09:42
@MalteHartwig wow, that does sound good, can you help me with implementation – Bhargav Feb 14 '18 at 09:46
@Bhargav then don't use `y.subList(2, 5);` and just create your target List manually. – achAmháin Feb 14 '18 at 09:49

score 1 · Accepted Answer · answered Feb 14 '18 at 09:49

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

    }

}

Malte Hartwig · Answer 3 · 2018-02-14T13:08:43.837

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

cool, nice job. You could use Collections.indexOfSublist to simplify — Gonen I, Feb 14 '18 at 12:36
@GonenI thanks for the great hint! I didn't know that one yet, guess I don't look at `Collections` often enough. Especially that they move some stuff to `Collection` directly. — Malte Hartwig, Feb 14 '18 at 13:10

Shuffle list except for certain sequences

3 Answers3