CODEWITHSUNDEEP
java
davewp
davewp

Reputation: 243

How can I randomize the iteration sequence of a Set?

I need to use the Set collection.

Each time I start a jvm to run the program, I want to iterate through the items in the Set in a randomly decided sequence.

The iteration sequence has nothing to do with the sequence in which I placed them in the Set, right?

So, what to do? How can I randomize the iteration sequence in a Set?

Here is my method, and it does not randomize. 

public static <T> void shuffle(Set<T> set) {
        List<T> shuffleMe = new ArrayList<T>(set);
        Collections.shuffle(shuffleMe);
        set.clear();
        set.addAll(shuffleMe);
    }

Upvotes: 2

Views: 11527

Answers (4)

dnault
dnault

Reputation: 8889

You could copy the contents of the Set into a List, shuffle the List, then return a new LinkedHashSet populated from the shuffled list. Nice thing about LinkedHashSet is that its iterators return elements in the order they were inserted.

public static <T> Set<T> newShuffledSet(Collection<T> collection) {
    List<T> shuffleMe = new ArrayList<T>(collection);
    Collections.shuffle(shuffleMe);
    return new LinkedHashSet<T>(shuffleMe);
}

Upvotes: 1

user177800
user177800

Reputation:

What you need is a RandomizingIterator

Set is unordered, so randomizing an unordered Collection doesn't make any logical sense.

An ordered Set is ordered using a Comparator which means it has a fixed order, you can't shuffle it, that has no meaning as the order is determined by the Comparator or the compare() method.

Set -> List will allow you to shuffle the contents of the List and then use a custom RandomizingIterator to iterate across the Set.

Example Implementation :

Link to Gist on GitHub - TestRandomizingIterator.java

import org.junit.Test;

import javax.annotation.Nonnull;
import java.util.*;

public class TestRandomzingIterator
{
    @Test
    public void testRandomIteration()
    {
        final Set<String> set = new HashSet<String>()
        {
            /** Every call to iterator() will give a possibly unique iteration order, or not */
            @Nonnull
            @Override
            public Iterator<String> iterator()
            {
                return new RandomizingIterator<String>(super.iterator());
            }

            class RandomizingIterator<T> implements Iterator<T>
            {
                final Iterator<T> iterator;

                private RandomizingIterator(@Nonnull final Iterator<T> iterator)
                {
                    List<T> list = new ArrayList<T>();
                    while(iterator.hasNext())
                    {
                        list.add(iterator.next());
                    }
                    Collections.shuffle(list);
                    this.iterator = list.iterator();
                }

                @Override
                public boolean hasNext()
                {
                    return this.iterator.hasNext();
                }

                @Override
                public T next()
                {
                    return this.iterator.next();
                }

            /**
             * Modifying this makes no logical sense, so for simplicity sake, this implementation is Immutable.
             * It could be done, but with added complexity.
             */
            @Override
            public void remove()
            {
                throw new UnsupportedOperationException("TestRandomzingIterator.RandomizingIterator.remove");
            }
            }
        };

        set.addAll(Arrays.asList("A", "B", "C"));

        final Iterator<String> iterator = set.iterator();
        while (iterator.hasNext())
        {
            System.out.println(iterator.next());
        }
    }
}

Notes:

This is a straw man example, but the intention is clear, use a custom Iterator to get custom iteration.

You can't get the normal iteration behavior back, but that doesn't seem to be a problem with your use case.

Passing the the super.iterator() to the facade is important, it will StackOverflowError otherwise, because it becomes a recursive call if you pass this to .addAll() or the List() constructor.

HashSet may appear to be ordered but it isn't guaranteed to stay ordered, the order depends on the hashCode of the objects and adding a single object may reorder the how the contents are order, the contract of the Set interface is that the order is undefined and in particular the HashSet is nothing more than a Facade over a backing Map.keySet().

There are other more supposedly light weight, but much more complex solutions that use the original Iterator and try and keep track of what has already been seen, those solutions aren't improvements over this technique unless the size of the data is excessively large, and the you are probably looking at on disk structures at that point.

Upvotes: 4

user3159253
user3159253

Reputation: 17455

Internally HashSet sorts all its elements, AFAIR according to their hash() value. So you should use other classes like SortedSet with a custom comparator. But remember the whole idea of Set is to find elements quickly, that's why it sorts elements internally. So you have to keep "stability" of the comparison. Maybe you don't need a set after shuffling?

Upvotes: 0

Logiraptor
Logiraptor

Reputation: 1518

According to the docs for java.util.Set:

The elements are returned in no particular order (unless this set is an instance of some class that provides a guarantee).

When you insert the elements there is no guarantee about the order they will be returned to you. If you want that behavior you will need to use a data structure which supports stable iteration order, e.g. List.

Upvotes: 0

Related Questions