Algorithm for generating not repeating, spaced-out RGB color values

Question

I want to have a static method, which whenever called will return a color value that didn't appear yet, and is not too close to last returned color (i.e. return new Color(last_value += 10) won't do). It also should be not random, so everytime the application is launched, the sequence of returned colors would be the same.

First thing that popped to my head, is to iterate over an array with a primal number step, something like this:

    private static HashMap<Integer, Boolean> used = new HashMap<>();
    private static int[] values = new int[0xfffff]; // 1/16th of possible colors
    private static int current = 0, jump = values.length / 7;

     public static Color getColour(){
        int value = values[current];
        used.put(current, true);
        current += jump;
        current %= values.length;
        //have some check here if all colors were used
        while (used.containsKey(current)){
            current++;
            current%=values.length;
        }
        return new Color(value);
    }

But I don't like it, since colors will be close to each other from some calls back.

Answer 1

A good way of generating non-repeating random-like sequences is using an LFSR.

/**
 * Linear feedback shift register
 *
 * Taps can be found at: See http://www.xilinx.com/support/documentation/application_notes/xapp052.pdf See http://mathoverflow.net/questions/46961/how-are-taps-proven-to-work-for-lfsrs/46983#46983 See
 * http://www.newwaveinstruments.com/resources/articles/m_sequence_linear_feedback_shift_register_lfsr.htm See http://www.yikes.com/~ptolemy/lfsr_web/index.htm See
 * http://seanerikoconnor.freeservers.com/Mathematics/AbstractAlgebra/PrimitivePolynomials/overview.html
 *
 * @author OldCurmudgeon
 */
public class LFSR implements Iterable<BigInteger> {

    // Bit pattern for taps.
    private final BigInteger taps;
    // Where to start (and end).
    private final BigInteger start;

    // The poly must be primitive to span the full sequence.
    public LFSR(BigInteger primitivePoly, BigInteger start) {
        // Where to start from (and stop).
        this.start = start.equals(BigInteger.ZERO) ? BigInteger.ONE : start;
        // Knock off the 2^0 coefficient of the polynomial for the TAP.
        this.taps = primitivePoly.shiftRight(1);
    }

    public LFSR(BigInteger primitivePoly) {
        this(primitivePoly, BigInteger.ONE);
    }

    // Constructor from an array of taps.
    public LFSR(int[] taps) {
        this(asPoly(taps));
    }

    private static BigInteger asPoly(int[] taps) {
        // Build the BigInteger.
        BigInteger primitive = BigInteger.ZERO;
        for (int bit : taps) {
            primitive = primitive.or(BigInteger.ONE.shiftLeft(bit));
        }
        return primitive;
    }

    @Override
    public Iterator<BigInteger> iterator() {
        return new LFSRIterator(start);
    }

    private class LFSRIterator implements Iterator<BigInteger> {
        // The last one we returned.

        private BigInteger last = null;
        // The next one to return.
        private BigInteger next = null;

        public LFSRIterator(BigInteger start) {
            // Do not return the seed.
            last = start;
        }

        @Override
        public boolean hasNext() {
            if (next == null) {
                /*
                 * Uses the Galois form.
                 *
                 * Shift last right one.
                 *
                 * If the bit shifted out was a 1 - xor with the tap mask.
                 */
                boolean shiftedOutA1 = last.testBit(0);
                // Shift right.
                next = last.shiftRight(1);
                if (shiftedOutA1) {
                    // Tap!
                    next = next.xor(taps);
                }
                // Never give them `start` again.
                if (next.equals(start)) {
                    // Could set a finished flag here too.
                    next = null;
                }
            }
            return next != null;
        }

        @Override
        public BigInteger next() {
            // Remember this one.
            last = hasNext() ? next : null;
            // Don't deliver it again.
            next = null;
            return last;
        }

        @Override
        public void remove() {
            throw new UnsupportedOperationException("Not supported.");
        }

        @Override
        public String toString() {
            return LFSR.this.toString()
                    + "[" + (last != null ? last.toString(16) : "")
                    + "-" + (next != null ? next.toString(16) : "") + "]";
        }
    }

    @Override
    public String toString() {
        return "(" + taps.toString(32) + ")-" + start.toString(32);
    }

}

Now you just need an 8+8+8=24 tap value.

Using it is simple.

public void test() {
    // Sample 24-bit tap found on page 5 of
    // http://www.xilinx.com/support/documentation/application_notes/xapp052.pdf
    int[] taps = new int[]{24, 23, 22, 17};
    LFSR lfsr = new LFSR(taps);
    int count = 100;
    for (BigInteger i : lfsr) {
        System.out.println("Colour: " + new Color(i.intValue()));
        if (--count <= 0) {
            break;
        }
    }
}

Features of an LFSR:

• It will repeat - but not until all possible bit patterns have been generated (except 0).
• The number generated is statistically a good random number.
• The same sequence will be generated each time (choose a different tap if you want a different sequence).

To achieve the spacing you require I would suggest you add a filter and discard any that are too close (by your criterion) to the previous one.