Algorithm for generating non-duplicate, spaced RGB color values

Question

I want to have a static method that when called will return a color value that has not yet appeared, and is not too close to the last returned color (i.e., return new Color(last_value += 10) will not). This should also not be random, so every time the application starts, the sequence of colors returned will be the same.

The first thing that appeared in my head was to iterate over the array in increments of the primary number, 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, because the colors will be close to each other from some callbacks.

Answer 1

A good way to generate non-repeating random sequences is to use 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 need to use the value 8+8+8=24 .

The use 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 LFSR:

• It will be repeated, but not until all possible bit patterns (except 0 ) are created.
• The generated number is a statistically good random number.
• The same sequence will be generated each time (select a different tap if you want a different sequence).

To achieve the required interval, I suggest you add a filter and drop everything that is too close (by your criteria) to the previous one.