Random permutation of IntStream

Question

Every now and then I find myself with indexed loops, for which I want to permutate the order to some random order. I usually transition from something like

for (int i = 0; i < max; i++) {
    // do stuff with i
}

to

List<Integer> indices = IntStream.range(0, max)
    .boxed()
    toCollection(() -> new ArrayList(max)));
Collections.shuffle(indices);
for (int i = 0; i < max; i++) {
    int index = indices.get(i);
    // do stuff with index
}

This is neither efficient nor elegant. Is it possible to create a Stream (ideally an IntStream) in a certain range, but have it return its elements shuffled? I am thinking of something along the lines of:

IntStream.range(0, max)
        .shuffled() // this method doesn't exist
        .forEach(IntConsumer::accept);

The resulting IntStream should still include all elements in the range [0, max) exactly once.

This is not a duplicate of this question, because I don't want to create a List and shuffle it. This solution has a massive overhead since it is working with Integers, while also redundantly creating and shuffling a List. I have provided that solution in my own example, so I am fully aware of that approach.

@NicholasK I don't want a `List` and shuffle it. I have provided that solution myself. I am asking for a solution which creates a shuffled `IntStream` in an elegant way — Neuron, Feb 19 '19 at 17:04
Folks, this is not a dup. The poster is saying that he finds the solution to the other question "neither efficient nor elegant" and is looking for a better way. — Willis Blackburn, Feb 19 '19 at 17:33
Did you look at [this solution](https://stackoverflow.com/a/36391959/1746118) as from the linked question as well? — Naman, Feb 19 '19 at 18:28
@nullpointer thanks for trying to find a solution, but yes, I have. Neither do I want to use an intermediary `List`, nor do I want to box my `int`s. — Neuron, Feb 19 '19 at 20:03
Why are you using `LinkedList` instead of `ArrayList`? Both operations, `shuffle` and iterating via index calling `get`, are horribly inefficient with this list type. In fact, most operations are. — Holger, Feb 20 '19 at 11:21
@Holger you are right. I coded this example in the Stackoverflow editor and didn't pay much attention to efficiency. It only served the purpose of showing what kind of solutions I am not looking for (meaning examples which collect to `List`s). — Neuron, Feb 20 '19 at 12:52

score 5 · Accepted Answer · answered Feb 19 '19 at 17:24

5

How about this? It's pretty much the same thing you have, except it encapsulates all the nitty gritty and just gives you a pure IntStream. Also it doesn't have to do so much boxing and unboxing.

public class ShuffledIntStream {

    public static IntStream to(int max) {
        Random r = new Random();
        int[] values = new int[max];
        for (int i = 0; i < max; i++) {
            values[i] = i;
        }
        for (int i = max; i > 1; i--) {
            swap(values, i - 1, r.nextInt(max));
        }
        return IntStream.of(values);
    }

    private static void swap(int[] values, int i, int j) {
        int temp = values[i];
        values[i] = values[j];
        values[j] = temp;
    }
}

answered Feb 19 '19 at 17:24

Willis Blackburn

8,068
19
36

I was hoping there would be a built in solution. But this solution is fast and it does what I asked for. Thanks! – Neuron Feb 19 '19 at 17:52
1

You can create the initial array using `int[] values = IntStream.range(0, max).toArray();`. Further, I’d use `Arrays.stream(values)` instead of the *varargs* method `IntStream.of(values)`. And for performance reasons, it’s recommended to replace `Random r = new Random();` with `ThreadLocalRandom r = ThreadLocalRandom.current();` – Holger Feb 20 '19 at 11:29

score 1 · Answer 2 · edited Feb 20 '19 at 13:52

1

You could use Random.ints:

new Random().ints(0, max)
    .distinct()
    .limit(max)
    .forEach(IntConsumer::accept);

ints will produce a stream of ints between 0 and max, distinct makes sure that there are no duplicates, and limit to get exactly how many you want.

edited Feb 20 '19 at 13:52

Neuron

5,141
5
38
59

answered Feb 19 '19 at 17:04

Thomas Francois

866
6
21

Maybe I have not made myself sufficiently clear, but I want all number in the 0-max range to occur exactly once. Like in a loop – Neuron Feb 19 '19 at 17:06
Isn't that what the call to distinct does? – Willis Blackburn Feb 19 '19 at 17:06
Ok, with that recent edit it looks like this does what I was asking for. Does this execute with performance `O(n)` or is the runtime indeterministic? – Neuron Feb 19 '19 at 17:07
@WillisBlackburn the original version of the answer didn't include that part. And edits done immediately after creating a post are not shown. So you'll have to trust me on that ;) – Neuron Feb 19 '19 at 17:08
3

It could repeatedly generate duplicate values that have to be filtered out by `distinct` so not exactly O(n). The first number will always be unique. For the i-th there is a `i/max` chance it will be a dup. So on the last number you'll probably have to generate another `max` values before happening across the one that's still unused. For `max = 10` that's probably okay, might be a bigger issue for larger values of `max`. – Willis Blackburn Feb 19 '19 at 17:15
@WillisBlackburn that's that what I thought. I will wait another day, if no answer comes along that provides a solution with O(n) runtime, I will accept yours. Thanks – Neuron Feb 19 '19 at 17:19

Random permutation of IntStream

2 Answers2