Algorithm for permutations and combinations.

[abhijit]

Hi Folks,
Need some help with math here.

I have to find out the number of combinations possible for a 6 character string.

The rules are as follows:

I can use all the 26 letters and digits from (0 - 9)
None of the strings should start with a letter.

eg:- A12345 is invalid. 12A345 is valid

None of the strings should end with a letter.

12345A is invalid. 12AB34 is valid.

None of the strings should start with a zero.
012A34 is invalid. 12A340 is valid.

Each output string should contain atleast one alphabet, but no more than 5 alphabets.

How do I start to figure this?

Help Folks,
abhijit

[dglienna]

You would need 6 loops, and in the middle of it, you would set up the rules to skip combos that are invalid. I assume you only want capital letters, but you didn't specify if you can have duplicates. What language are you working with?

If it's VB6, then I may be able to help, but you should really start it off yourself.
Post what you come up with, and any problems you have.

You can use integers for the loop, and use the chr$() function to generate a letter or number.

[abhijit]

You would need 6 loops, and in the middle of it, you would set up the rules to skip combos that are invalid. I assume you only want capital letters, but you didn't specify if you can have duplicates. What language are you working with?

If it's VB6, then I may be able to help, but you should really start it off yourself.
Post what you come up with, and any problems you have.

You can use integers for the loop, and use the chr$() function to generate a letter or number.

I am working with VB5.
You are right. I can't have duplicates.
I cannot have lower case letters.

First I need help in counting how many combinations does that make up. I am a bit weak in math, so I am asking for help.

Regards,
Abhijit

[Shaggy Hiker]

Well, since the first character can only be a number from 1 to 9, then there are 9 combinations.

For the second letter there can only be 34 possibilities since there could be any of 26 letters, but only nine numbers (one was used for the first digit, and if it can't be repeated, that leaves only nine possible numbers).

For the third letter, there would be only 33 possiblities since there is one less option than in the previous letter.

The same holds true for the fourth and fifth character.

Up to this point, the math would be: 9 * 34 * 33 * 32 * 31

Now it gets sticky. The last character must be a number from 0 to 9 because it can't be a letter, and 0 is not excluded. However, one of the digits has been used in the first character, so there can be at MOST 9 digits available. Unfortunately, up to three other characters could be digits. Therefore, the LEAST number of digits available for the final character is 10 - 4 = 6.

Thus, the number of permutations is at Most:
9 * 34 * 33 * 32 * 31 * 9 = 90,154,944

But could be as small as:
9 * 34 * 33 * 32 * 31 * 6 = 60,103,296

[abhijit]

Here is the math I worked out.

1st Place = 9 ways
6th Place = 10 ways

2nd - 5th place = 36 ways

So the answer could be 9 * 10 * (36 ^ 4)
= 151165440

Let me know if something is wrong.

Cheers,
Abhijit

[Shaggy Hiker]

It depends on repeating characters. If you can't repeat ANY of the characters, then there aren't 10 characters available for the 6th place, because one of them would have been used in the 1st place. The same problem exists for the 2nd through 5th places. Each time a character is used, the number of available characters for the next characters has been reduced by one. I think I had that laid out in the earlier post.

If you can duplicate characters, then your calculation is correct.

[abhijit]

With the string, you can always have duplicate characters.
For example "1AA220" is perfectly valid. So 150 million (+) possibilities exist.

Now that I have got the numbering right, I need to start on the logic for this thing. Luckily I have time till 10th of Jan 2006.

[Shaggy Hiker]

Ah, I thought you had said earlier that you can't have duplicates. Since you can, then your math is correct.

The first and last characters are easy, because you can just use Rnd for them. As for the middle loops, look at the ASCII chart. I can't look it up right now, but I believe the numbers and letters are contiguous. Therefore, pick a random number in the range of the numbers and letters, and you have a randomly selected, valid character. Convert the ASCII code to text, and you have a value for characters 2-5.

[abhijit]

Ok. I meant duplicates within the series. Your math is correct too.

Thanks for your help. No I wouldn't want anything random. I need a sequential order to this. This is my primary key.

[Shaggy Hiker]

I was beginning to suspect that. I did something like this a few years ago in VB6. The solution I had was to figure out something likely, and try to add it. This would throw an error if the item was already in the key, at which point I would move to the next one, etc.

This isn't a particularly good idea, but I think it is still functional in VB5/6. Exception handling in .NET seems a bit slower.

[dglienna]

Do you need to figure out the number of possiblilties, or do you want to generate the actual numbers that would be generated?