Random Number Generator: mainly how to stop repeti

Question

So I'm working on an OOP program that is meant to create 50 unique numbers, by using a random number generator that ensures no repeating numbers. I have the random part down and I'm using an extra method which swaps the numbers but I don't know to only swap number if they are already used, I hope this is understandable.

import java.util.Random;
public class Project_1
{

    public static void main(String[] args)
    {
        Random rand = new Random();
        int a[][] = new int[11][6];
        for (int i = 1; i <= 10; i++) //row of values which fill in Student number
        {
            System.out.print("Student " + i + ":");
            System.out.print("\t");
            for (int j = 1; j <= 5; j++) //j is limited up to 5 columns
            {
                a[i][j] = 1 + rand.nextInt(50);
                CheckNumbers(a[i][j]); //input of the checkNumbers method
                System.out.print(a[i][j] + "\t"); // meaning that the numbers fill out according to table coordinates
            }
            System.out.println();
        }
    }

    public static void CheckNumbers(int[] x, int[] y)
    {
        int temp;
        for (int j = 0; j < 50; j++) //j must start at 1??? and we have 50 iterations, so countercontrolled to 50?
        {
            temp = x[i]; //this can be used to swap the numbers
            x[i] = y[i];
            y[i] = temp;
        }
    }
}

This is my program and if ran without the input of the CheckNumbers method my answer was

 ----jGRASP exec: java Project_1

Student 1:  8   35  8   5   40  
Student 2:  46  3   44  40  8   
Student 3:  27  47  28  11  3   
Student 4:  30  25  43  8   34  
Student 5:  3   12  45  6   5   
Student 6:  19  37  33  14  14  
Student 7:  9   31  6   39  32  
Student 8:  16  6   23  28  31  
Student 9:  19  34  49  42  11  
Student 10: 26  3   17  16  15  

 ----jGRASP: operation complete.

However as you see 8 is repeated (among may other numbers) so I put in the CheckNumbers method to stop it but I have an error filled compile message... so I am assuming that I have many errors in my CheckNumbers, so I need major help with that too.

Thank you all for your help!!!!

Answer 1

Xincrol algorithm solves this problem. Explanation + source code:

http://openpatent.blogspot.co.il/2013/04/xincrol-unique-and-random-number.html

/**
 * Xincrol - Unique and Random Number Generator
 * Xincrol.java
 * Purpose: Generating unique random numbers in specified range.
 *
 * @author Tofig Kareemov
 * @version 1.2 2013.04.28
 */
package androphic.estereos.lib.algs;

public class Xincrol {
    // Private Data...
    private int iUniqueSeed = 0;
    private int[] iKey = new int[8];
    private int iSet = 0;
    private int iSystemID = 0;

    // Constructor
    public Xincrol() {
        iSystemID = System.getProperties().toString().hashCode();
        for (int i = 0; i < iKey.length; ++i) {
            iKey[i] = i;
        }
        reset(Integer.MAX_VALUE);
    }

    // .

    // Private Methods...
    private void reset(int iBase) {
        iUniqueSeed = 0;
        iKey[0] ^= iSystemID;
        iKey[1] ^= (int) System.nanoTime();
        iKey[2] ^= (int) (System.nanoTime() >> 32);
        iKey[3] ^= (int) System.currentTimeMillis();
        iKey[4] ^= (int) (System.currentTimeMillis() >> 32);
        iKey[5] ^= 0xa5a5a5a5;
        iKey[6] ^= 0x5a5a5a5a;
        iKey[7] ^= 0xff00ff00;
        int iGlue = iKey[iKey.length - 1];
        int iBaseMask = iBase - 1;
        for (int i1 = 0; i1 < 2; ++i1) {
            for (int i = 0; i < iKey.length; ++i) {
                iGlue = iGlue ^ iKey[i] ^ i;
                if ((iKey[i] & 1) == 0) {
                    iGlue = INC(iGlue, iBaseMask);
                } else {
                    iGlue = DEC(iGlue, iBaseMask);
                }
                if ((iKey[i] & 2) == 0) {
                    iGlue = ROL(iGlue, iBaseMask);
                } else {
                    iGlue = ROR(iGlue, iBaseMask);
                }
                iKey[i] = XOR(iGlue, iKey[i], iBaseMask);
            }
        }
        iSet = iKey[iKey.length - 1] & 3;
    }

    // Set 1 Function
    private int XOR(int iA, int iB, int iBaseMask) {
        return ((iA ^ iB) & iBaseMask);
    }

    private int INC(int iA, int iBaseMask) {
        return ((++iA) & iBaseMask);
    }

    private int ROL(int iA, int iBaseMask) {
        iA <<= 1;
        if (iA > iBaseMask) {
            iA |= 1;
        }
        return (iA & iBaseMask);
    }

    // .

    // Set 2 Functions
    private int DEC(int iA, int iBaseMask) {
        return ((--iA) & iBaseMask);
    }

    private int ROR(int iA, int iBaseMask) {
        if ((iA & 0x00000001) == 1) {
            return ((iA >>> 1) & iBaseMask) | ((iBaseMask + 1) >>> 1);
        } else {
            return ((iA >>> 1) & iBaseMask);
        }
    }

    // .
    // .

    // Public Methods

    public synchronized void randomize(int iRange) {
        int iBase = 1;

        if (iRange <= 0) {
            return;
        }
        for (; iBase < iRange; iBase <<= 1) {
        }
        reset(iBase);
    }

    public int incdec(int iA, int iSet, int iBaseMask) {
        switch (iSet) {
        case 0:
            return INC(iA, iBaseMask);
        case 1:
            return DEC(iA, iBaseMask);
        case 2:
            return INC(iA, iBaseMask);
        case 3:
            return DEC(iA, iBaseMask);
        default:
            return 0;
        }
    }

    public int rolror(int iA, int iSet, int iBaseMask) {
        switch (iSet) {
        case 0:
            return ROL(iA, iBaseMask);
        case 1:
            return ROL(iA, iBaseMask);
        case 2:
            return ROR(iA, iBaseMask);
        case 3:
            return ROR(iA, iBaseMask);
        default:
            return 0;
        }
    }

    public synchronized int next(int iRange) {
        int iResult = iRange;
        int iBase = 1;

        for (; iBase < iRange; iBase <<= 1) {
        }
        if ((iKey == null) || (iUniqueSeed >= iBase)) {
            reset(iBase);
        }
        int iBaseMask = iBase - 1;
        for (int i = 0; (i < iBase) && (iResult >= iRange); ++i) {
            iUniqueSeed = (++iUniqueSeed) % iBase;
            iResult = iUniqueSeed;
            for (int i1 = 0; i1 < iKey.length; ++i1) {
                iResult = XOR(iResult, iKey[i1], iBaseMask);
                for (int i2 = iKey[i1] | iBase; i2 > 1; i2 >>>= 1) {
                    if ((i2 & 1) == 1) {
                        iResult = incdec(iResult, iSet, iBaseMask);
                    } else {
                        iResult = rolror(iResult, iSet, iBaseMask);
                    }
                }
            }
        }
        return iResult;
    }

    public synchronized int prev(int iRange) {
        int iResult = iRange;
        int iBase = 1;

        if (iRange <= 0) {
            return 0;
        }
        for (; iBase < iRange; iBase <<= 1) {
        }
        if ((iKey == null) || (iUniqueSeed >= iBase)) {
            reset(iBase);
        }
        int iBaseMask = iBase - 1;
        for (int i = 0; (i < iBase) && (iResult >= iRange); ++i) {
            iUniqueSeed = (--iUniqueSeed) % iBase;
            iResult = iUniqueSeed;
            for (int i1 = 0; i1 < iKey.length; ++i1) {
                iResult = XOR(iResult, iKey[i1], iBaseMask);
                for (int i2 = iKey[i1] | iBase; i2 > 1; i2 >>>= 1) {
                    if ((i2 & 1) == 1) {
                        iResult = incdec(iResult, iSet, iBaseMask);
                    } else {
                        iResult = rolror(iResult, iSet, iBaseMask);
                    }
                }
            }
        }
        return iResult;
    }

    public synchronized int random(int iRange) {
        randomize(iRange);
        return iKey[iKey.length - 1];
    }

    // .

    public static void main(String[] args) {
        Xincrol oXincrol = new Xincrol();
        int iRange = 10;
        int iTries = 100;
        int iValueStringLength = ("" + (iRange - 1)).length();
        int[] iTest = new int[iRange];
        for (int i1 = 0; i1 < iTries; ++i1) {
            for (int i2 = 0; i2 < iRange; ++i2) {
                // Printing progress
                if (i2 == 0) {
                    System.out.print("" + (i1 * 100 / iTries) + "%, " + i1
                            + ": ");
                }
                // Generating
                iTest[i2] = oXincrol.next(iRange);
                // Printing values
                String s = "" + iTest[i2];
                for (; s.length() < iValueStringLength; s = " " + s) {
                }
                System.out.print(s);
                // Printing end of line
                if (i2 == iRange - 1) {
                    System.out.println();
                    // Testing for successful generation
                    boolean bSuccess = false;
                    for (int i3 = 0; i3 < iTest.length; ++i3) {
                        bSuccess = false;
                        for (int i4 = 0; i4 < iTest.length; ++i4) {
                            if (iTest[i4] == i3) {
                                bSuccess = true;
                            }
                        }
                        if (!bSuccess) {
                            System.out.println("Error!!!");
                            System.exit(1);
                        }
                    }
                    // Randomizing for the next line
                    System.out.flush();
                    oXincrol.randomize(iRange);
                } else {
                    System.out.print(",");
                }
            }
        }
        System.out.println("Success!!!");
    }
}

Answer 2

Your method definition of CheckNumbers is incorrect.

It should receive int[][] and not two int[] int[].

However its fairly impossible for me to figure out what the intent of that method is.

Answer 3

Do you have to generate the IDs yourself using java.util.Random? I would use java.lang.UUID which will generate an immutable universally unique identifier.

Answer 4

I'm not going to correct your methods. But if you want to create a random without repeating, create your own custom class.

import java.util.BitSet;
import java.util.Random;

/**
 * Random number generator without repeat in the given range at construction time.
 * 
 * @author martijn
 */
public class NoRepeatRandom {

    private Random random;
    private BitSet used;
    private int max;

    /**
     * Creates new instance of NoRepeatRandom, with the range <code>[0-max[</code>.
     * @param max the maximum for the range
     * @param seed the seed for the underlying {@link java.util.Random}
     */
    public NoRepeatRandom(int max, long seed)
    {
        this.max = max;
        this.used = new BitSet(max);
        this.random = new Random(seed);
    }

    /**
     * Creates new instance of NoRepeatRandom, with the range <code>[0-max[</code>.<br />
     * <code>System.currentTimeMillis()</code> is used as seed for the underlying {@link java.util.Random}
     * @param max the maximum for the range
     */
    public NoRepeatRandom(int max)
    {
        this(max, System.currentTimeMillis());
    }

    /**
     * Gives the next random number
     * @return a new random number. When finished it returns -1.
     */
    public int next()
    {
        if (isFinished())
        {
            return -1;
        }
        while (true)
        {
            int r = random.nextInt(max);
            if (!used.get(r))
            {
                used.set(r);
                return r;
            }
        }
    }

    /**
     * Tells if the random generator has finished. Which means that all number in the range
     * [0-max[ are used.
     * @return true if all numbers are used, otherwise false.
     */
    public boolean isFinished()
    {
        return max == used.cardinality();
    }

    /**
     * Sets all the numbers in the range [0-max[ to unused. Which means that all the numbers
     * can be reused.
     */
    public void reset()
    {
        used.clear();
    }

    /**
     * 
     * @return the maximum.
     */
    public int getMax()
    {
        return max;
    }
}

Usage:

NoRepeatRandom myRandom = new NoRepeatRandom(50);
for (int i = 0; i < myRandom.getMax(); ++i)
    System.out.println(myRandom.next());

EDIT: JavaDoc added!!

Answer 5

I use Collections.shuffle(<List>) to generate random numbers. It is very quick way to generate numbers with minimum lines of code.

First create an Integer array and will it with number of integers that you want to randomize. In the below example I have considered 10. Then use Collections.shuffle(<List>) to randomize the Integer array. Then print out the array.

Integer[] randInt = new Integer[10]; //where 10 is the max random integers
for (int i = 0; i < 10; i++) randInt[i] = i;
Collections.shuffle(Arrays.asList(randInt));
for (int i = 0; i < 10; i++) System.out.printtln (randInt[i] = i);

Answer 6

Handy way to get non-repeating list of numbers in random order:

Create an ArrayList with ints from 1 - 50

Use Collections.Shuffle

(you also should fix your nested loop and allocations so your indices start at 0 consistently-- but to learn you should do some of this yourself)