CODEWITHSUNDEEP
javascalajava-stream
deamon
deamon

Reputation: 92519

Shuffle a list of integers with Java 8 Streams API

I tried to translate the following line of Scala to Java 8 using the Streams API:

// Scala
util.Random.shuffle((1 to 24).toList)

To write the equivalent in Java I created a range of integers:

IntStream.range(1, 25)

I suspected to find a toList method in the stream API, but IntStream only knows the strange method:

collect(
  Supplier<R> supplier, ObjIntConsumer<R> accumulator, BiConsumer<R,R> combiner)

How can I shuffle a list with Java 8 Streams API?

Upvotes: 44

Views: 50568

Answers (8)

sigpwned
sigpwned

Reputation: 7453

If you're looking for a "streaming only" solution and a deterministic, merely "haphazard" ordering versus a "random" ordering is Good Enough, you can always sort your ints by a hash value:

List<Integer> xs=IntStream.range(0, 10)
    .boxed()
    .sorted( (a, b) -> hashCode(a) - hashCode(b) )
    .collect(Collectors.toList());

If you'd rather have an int[] than a List<Integer>, you can just unbox them afterwards. Unfortunately, you have go through the boxing step to apply a custom Comparator, so there's no eliminating that part of the process.

List<Integer> ys=IntStream.range(0, 10)
    .boxed()
    .sorted( (a, b) -> hashCode(a) - hashCode(b) )
    .mapToInt( a -> a.intValue() )
    .toArray();

While it's tempting to use Integer.hashCode() as the hash code implementation, that method returns the original int value, as @StephenC helpfully pointed out in the comments, so that would actually be a very poor choice, since it would produce a sorted list.

Here are some better options to consider:

Guava

If you're already using guava, then any of the 32-bit hash functions in the Hashing class (e.g., crc32c, murmur3_32_fixed, etc.) would be excellent choices.

murmurHash3

MurmurHash3 has a simple variant specifically tailored for 32-bit integers, the so-called finalization avalanche:

public static int murmurHash3(int key) {
    key ^= key >>> 16;
    key *= 0x85ebca6b;
    key ^= key >>> 13;
    key *= 0xc2b2ae35;
    key ^= key >>> 16;
    return key;
}

Knuth

Knuth's Multiplicative Hash from The Art of Computer Programming is another good option:

public static int knuth(int key) {
    int hash = key * 0x9e3779b9;  // Knuth's multiplicative constant for 32-bit hashing
    return hash ^ (hash >>> 16);   // Mix the bits with XOR and right shift
}

Upvotes: 2

Ron McLeod
Ron McLeod

Reputation: 691

List<Integer> randomShuffledRange(int startInclusive, int endExclusive) {
    return new Random().ints(startInclusive, endExclusive)
            .distinct()
            .limit(endExclusive-startInclusive)
            .boxed()
            .collect(Collectors.toList());
}

var shuffled = randomShuffledRange(1, 10);
System.out.println(shuffled);

Example output:

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

Upvotes: 1

Grzegorz Piwowarek
Grzegorz Piwowarek

Reputation: 13823

If you want to process the whole Stream without too much hassle, you can simply create your own Collector using Collectors.collectingAndThen():

public static <T> Collector<T, ?, Stream<T>> toEagerShuffledStream() {
    return Collectors.collectingAndThen(
      toList(),
      list -> {
          Collections.shuffle(list);
          return list.stream();
      });
}

But this won't perform well if you want to limit() the resulting Stream. In order to overcome this, one could create a custom Spliterator:

package com.pivovarit.stream;

import java.util.List;
import java.util.Objects;
import java.util.Random;
import java.util.RandomAccess;
import java.util.Spliterator;
import java.util.function.Consumer;
import java.util.function.Supplier;

class ImprovedRandomSpliterator<T, LIST extends RandomAccess & List<T>> implements Spliterator<T> {

    private final Random random;
    private final List<T> source;
    private int size;

    ImprovedRandomSpliterator(LIST source, Supplier<? extends Random> random) {
        Objects.requireNonNull(source, "source can't be null");
        Objects.requireNonNull(random, "random can't be null");

        this.source = source;
        this.random = random.get();
        this.size = this.source.size();
    }

    @Override
    public boolean tryAdvance(Consumer<? super T> action) {
        if (size > 0) {
            int nextIdx = random.nextInt(size);
            int lastIdx = --size;

            T last = source.get(lastIdx);
            T elem = source.set(nextIdx, last);
            action.accept(elem);
            return true;
        } else {
            return false;
        }
    }

    @Override
    public Spliterator<T> trySplit() {
        return null;
    }

    @Override
    public long estimateSize() {
        return source.size();
    }

    @Override
    public int characteristics() {
        return SIZED;
    }
}

and then:

public final class RandomCollectors {

    private RandomCollectors() {
    }

    public static <T> Collector<T, ?, Stream<T>> toImprovedLazyShuffledStream() {
        return Collectors.collectingAndThen(
          toCollection(ArrayList::new),
          list -> !list.isEmpty()
            ? StreamSupport.stream(new ImprovedRandomSpliterator<>(list, Random::new), false)
            : Stream.empty());
    }

    public static <T> Collector<T, ?, Stream<T>> toEagerShuffledStream() {
        return Collectors.collectingAndThen(
          toCollection(ArrayList::new),
          list -> {
              Collections.shuffle(list);
              return list.stream();
          });
    }
}

I explained the performance considerations here: https://4comprehension.com/implementing-a-randomized-stream-spliterator-in-java/

Upvotes: 6

Paul Boddington
Paul Boddington

Reputation: 37655

You may find the following toShuffledList() method useful.

private static final Collector<?, ?, ?> SHUFFLER = Collectors.collectingAndThen(
        Collectors.toCollection(ArrayList::new),
        list -> {
            Collections.shuffle(list);
            return list;
        }
);

@SuppressWarnings("unchecked")
public static <T> Collector<T, ?, List<T>> toShuffledList() {
    return (Collector<T, ?, List<T>>) SHUFFLER;
}

This enables the following kind of one-liner:

IntStream.rangeClosed('A', 'Z')
         .mapToObj(a -> (char) a)
         .collect(toShuffledList())
         .forEach(System.out::print);

Example output:

AVBFYXIMUDENOTHCRJKWGQZSPL

Upvotes: 52

kozla13
kozla13

Reputation: 1942

This is my one line solution: I am picking one random color:

colourRepository.findAll().stream().sorted((o1,o2)-> RandomUtils.nextInt(-1,1)).findFirst().get()

Upvotes: -2

Xavier
Xavier

Reputation: 1574

You can use a custom comparator that "sorts" the values by a random value:

public final class RandomComparator<T> implements Comparator<T> {

    private final Map<T, Integer> map = new IdentityHashMap<>();
    private final Random random;

    public RandomComparator() {
        this(new Random());
    }

    public RandomComparator(Random random) {
        this.random = random;
    }

    @Override
    public int compare(T t1, T t2) {
        return Integer.compare(valueFor(t1), valueFor(t2));
    }

    private int valueFor(T t) {
        synchronized (map) {
            return map.computeIfAbsent(t, ignore -> random.nextInt());
        }
    }

}

Each object in the stream is (lazily) associated a random integer value, on which we sort. The synchronization on the map is to deal with parallel streams.

You can then use it like that:

IntStream.rangeClosed(0, 24).boxed()
    .sorted(new RandomComparator<>())
    .collect(Collectors.toList());

The advantage of this solution is that it integrates within the stream pipeline.

Upvotes: 16

Andrey Chaschev
Andrey Chaschev

Reputation: 16526

Here you go:

List<Integer> integers =
    IntStream.range(1, 10)                      // <-- creates a stream of ints
        .boxed()                                // <-- converts them to Integers
        .collect(Collectors.toList());          // <-- collects the values to a list

Collections.shuffle(integers);

System.out.println(integers);

Prints:

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

Upvotes: 49

Peter Lawrey
Peter Lawrey

Reputation: 533740

To perform a shuffle efficiently you need all the values in advance. You can use Collections.shuffle() after you have converted the stream to a list like you do in Scala.

Upvotes: 3

Related Questions