CODEWITHSUNDEEP
javaalgorithm
Scruffers
Scruffers

Reputation: 5074

Generating a non-repeating list of alpha-numeric codes

I'm trying to generate a list of non-repeating alpha-numeric codes. They will be generated in batches and in volumes such that it won't be feasible to explicitly look at what has been generated before - i.e. uniqueness needs to be somehow guaranteed without recourse to previous codes outside the current batch.

The codes should have a length of 8 characters with the constraint that certain characters cannot appear in the code (e.g. l and L) since a user will be re-entering these at a later date.

I'll probably implement this in Java, but I'd appreciate any algorithms or tricks anyone can think of for solving this...

Regards,

Upvotes: 1

Views: 2884

Answers (7)

Barani
Barani

Reputation: 58

Check this logic. You can exclude any alphabet or number in loop. For your question of 'L', you can exclude as follows

        if(brokenCode[i] == 'K') brokenCode[i] = 'L'; 
        brokenCode[i] = (char)(((int)brokenCode[i]) + 1);

Sample code

class Rextester
{  
    public static void main(String args[])
    {
        String currCode = "00000000";
        for(int i=0; i<2000; i++)
        {
            System.out.println(currCode);
            currCode = getNextCode(currCode);
        }
    }

    private static String getNextCode(String currCode)
    {
        char [] brokenCode;
        brokenCode = currCode.toCharArray();
        for(int i=brokenCode.length-1; i>= 0; i--)
        {
            if(brokenCode[i] == '9')
            {
                brokenCode[i] = 'A';
                break;
            }
            if(brokenCode[i] == 'Z'){
                brokenCode[i] = '0';
                continue;
            }
            brokenCode[i] = (char)(((int)brokenCode[i]) + 1);
            break;
        }
        currCode = new String(brokenCode);
        return currCode;
    }

}

Upvotes: 0

700 Software
700 Software

Reputation: 87853

Can you iterate forward like this?

000000a1 000000a2 000000a3 ... 000000ay 000000az 000000b0

Then just remember the last number and all future numbers will be greater than the last one

You may find this useful 

long l = 20492;
String s = "wogjz";
s = Long.toString(l, 26+10-2).replace('I','Y').replace('L','Z') // convert long number to string (with letters)
l = Long.parseLong(s.replace('Y','I').replace('Z','L'), 26+10-2) + 1) // Convert string to number

The number 26+10-2 is number of letters plus number of digits minus number of forbidden letters (I and L). The I/Y and Z/L conversion is to use the last letters of the alphabet in cooperation with the Java Library.

You will want to make sure the user does not enter I or L by yourself because my code will not work right otherwise.

You will want to add leading zeros to the string until it reaches 8 characters

Also my program does not know the difference between big and small letters. If you need that then the app would have to be more complex because we would need an array instead of just one long number.

Upvotes: 0

Pablo Venturino
Pablo Venturino

Reputation: 5318

Too bad you're constrained to 8 characters. Otherwise, you could have used the MD5 class to generate unique codes.

Anyway, if you want to ensure your codes will be unique, you can encode the generation date in some of your code characters to ensure it won't conflict with previous codes.

For instance, your code would have the form YMDXXXXX, where:

  • Y is the year since 2010 (start with 0, and start using letters when you run out of numbers in 2020)
  • M is the month (same criteria)
  • D is the day (won't be larger than 31, so chars 0-9A-Z should be enough)
  • X are the codes generated on your current batch.

Upvotes: 0

AlexR
AlexR

Reputation: 115378

8 nested loops solve your problem trivially. Moreover if you want you can use Random to generate next token and store all tokens in Set. Every time you get new token check whether it is already in set.

Upvotes: 0

Peter Lawrey
Peter Lawrey

Reputation: 533750

You could just encode an atomic counter such as

AtomicInteger counter = new AtomicInteger();

public String generateId() {
   return Integer.toHexString(counter.getAndIncrement());
}

This will give you 4 billion unique ids.

If you need more than 4 billion, you can use an AtomicLong and use your own encoding for that number depending on which characters you want to allow.

Upvotes: 3

NPE
NPE

Reputation: 500773

The problem as stated has the obvious solution, which is to generate the codes sequentially starting from zero. Think of each code as a number in base-34 (the digits being 0-9 and A-Z except I and L). If this is not what you want you might like to clarify the question (e.g. do you want randomness?)

edit: This of course requires you to remember the last code you generated, and carry this one piece of information across batches.

Upvotes: 2

pauljwilliams
pauljwilliams

Reputation: 19225

Just take System.currentTimeMillis and encode it alphanumerically by mapping each digit to a letter. Keep track of the last one issued (to guard againts multiple generations in the same millisecond) and handle accordingly.

Upvotes: 4

Related Questions