Package squidpony.squidmath

Class ShuffledIntSequence

java.lang.Object
squidpony.squidmath.LowStorageShuffler
squidpony.squidmath.ShuffledIntSequence
All Implemented Interfaces:
Serializable
public class ShuffledIntSequence
extends LowStorageShuffler
implements Serializable
An infinite sequence of pseudo-random ints (typically used as indices) from 0 to some bound, with all possible ints returned in a shuffled order before re-shuffling for the next result. Does not store the sequence in memory. Uses a Feistel network, as described in this post by Alan Wolfe. The API is very simple; you construct a ShuffledIntSequence by specifying how many items it should shuffle (the actual sequence is boundless, but the items it can return are limited to between 0 and some bound), and you can optionally use a seed (it will be random if you don't specify a seed). Call next() on a ShuffledIntSequence to get the next distinct int in the shuffled ordering; next() will re-shuffle the sequence if it runs out of distinct possible results. You can go back to the previous item with previous(), which is allowed to go earlier than the first result generated (it will jump back to what is effectively the previous shuffled sequence). You can restart the sequence with LowStorageShuffler.restart() to use the same sequence over again (which doesn't make much sense here, since this makes many sequences by re-shuffling), or restart(int) to use a different seed (the bound is fixed).
This differs from the version in Alan Wolfe's example code and blog post; it uses a very different round function, and it only uses 2 rounds of it (instead of 4). Wolfe's round function is MurmurHash2, but as far as I can tell the version he uses doesn't have anything like MurmurHash3's fmix32() to adequately avalanche bits, and since all keys are small keys with the usage of MurmurHash2 in his code, avalanche is the most important thing. It's also perfectly fine to use irreversible operations in a Feistel network round function, and I do that since it seems to improve randomness slightly. The LowStorageShuffler.round(int, int) method used here acts like SilkRNG's way of mixing two states, but here changed to be irreversible and unbalanced (which is fine here). Using 4 rounds turns out to be overkill in this case. This also uses a different seed for each round.
This class extends LowStorageShuffler, changing it from producing a unique set of ints once, to producing many sets of ints one after the next.
Created by Tommy Ettinger on 9/30/2018.
Author:
Alan Wolfe, Tommy Ettinger
See Also:
Serialized Form

  • Field Summary

    Fields 
    Modifier and Type Field Description
    protected int seed  

    Fields inherited from class squidpony.squidmath.LowStorageShuffler

    bound, halfBits, index, key0, key1, leftMask, pow4, rightMask

  • Constructor Summary

    Constructors 
    Constructor Description
    ShuffledIntSequence()
    Constructs a ShuffledIntSequence with a random seed and a bound of 10.
    ShuffledIntSequence​(int bound)
    Constructs a ShuffledIntSequence with the given exclusive upper bound and a random seed.
    ShuffledIntSequence​(int bound, int seed)
    Constructs a ShuffledIntSequence with the given exclusive upper bound and int seed.

  • Method Summary

    Modifier and Type Method Description
    int next()
    Gets the next distinct int in the sequence, shuffling the sequence if it has been exhausted so it never runs out.
    int previous()
    Gets the previous returned int from the sequence (as yielded by next()), restarting the sequence in a correctly-ordered way if it would go to before the "start" of the sequence (it is actually close to infinite both going forwards and backwards).
    void restart​(int seed)
    Starts the sequence over, but can change the seed (completely changing the sequence).

    Methods inherited from class squidpony.squidmath.LowStorageShuffler

    determine, encode, restart, round

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Field Details

  • Constructor Details

    • ShuffledIntSequence

      public ShuffledIntSequence()
      Constructs a ShuffledIntSequence with a random seed and a bound of 10.

    • ShuffledIntSequence

      public ShuffledIntSequence​(int bound)
      Constructs a ShuffledIntSequence with the given exclusive upper bound and a random seed.
      Parameters:
      bound - how many distinct ints this can return

    • ShuffledIntSequence

      public ShuffledIntSequence​(int bound, int seed)
      Constructs a ShuffledIntSequence with the given exclusive upper bound and int seed.
      Parameters:
      bound - how many distinct ints this can return
      seed - any int; will be used to get several seeds used internally

  • Method Details

    • next

      public int next()
      Gets the next distinct int in the sequence, shuffling the sequence if it has been exhausted so it never runs out.
      Overrides:
      next in class LowStorageShuffler
      Returns:
      the next item in the sequence

    • previous

      public int previous()
      Gets the previous returned int from the sequence (as yielded by next()), restarting the sequence in a correctly-ordered way if it would go to before the "start" of the sequence (it is actually close to infinite both going forwards and backwards).
      Overrides:
      previous in class LowStorageShuffler
      Returns:
      the previously-given item in the sequence, or -1 if something goes wrong (which shouldn't be possible)

    • restart

      public void restart​(int seed)
      Starts the sequence over, but can change the seed (completely changing the sequence). If seed is the same as the seed given in the constructor, this will use the same sequence, acting like LowStorageShuffler.restart().
      Overrides:
      restart in class LowStorageShuffler
      Parameters:
      seed - any int; will be used to get several seeds used internally