5 Replies - 2557 Views - Last Post: 11 February 2014 - 10:39 PM

#1 xilith117  Icon User is offline

  • D.I.C Head

Reputation: 3
  • View blog
  • Posts: 99
  • Joined: 13-August 11

I need to figure out the number of possible combinations

Posted 10 February 2014 - 10:16 PM

I am writing a program to generate activation codes for a product I am releasing (NOT to "crack" the code of a different product.) My program works fine so far and generates the code but I am not quite sure how to calculate the number of possible combinations. Here is an example of how it works:

working code examples: A47X3,R28X2,X21X9, T49X1

The first Char is a random letter (it can not be "O" so people wont mistake it for 0)

The second is a number between 1 and 4
the third is a number between 1 and 9
The fourth is always X
The fifth is a number between 1 and 9

so 25x4x9x9 = 8100 WOULD be my answer but there is one more rule to this code that complicates it.
The second Char + the First third char + the fifth char must equal either 12 or 14. I do not know how to calculate the number of combinations taking this into consideration.

Mods, please move my post if there is a better area for it.

This post has been edited by xilith117: 10 February 2014 - 10:48 PM


Is This A Good Question/Topic? 1
  • +

Replies To: I need to figure out the number of possible combinations

#2 macosxnerd101  Icon User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12147
  • View blog
  • Posts: 45,157
  • Joined: 27-December 08

Re: I need to figure out the number of possible combinations

Posted 10 February 2014 - 10:35 PM

There are 26 letters in the alphabet, not 25. So your first term should be a 25.

For your constraints, I'd use a generating function to count this, with f(x) = (1 + x + x^2 + x^3) * (1 + x + x^2 + x^3 + x^4 + x^5 + x^7 + x^8)^2. Then add the coefficients of x^9 and x^11.

I got the generating function from the Diophantine equation: a + b + c = 12, with 1 <= a <= 4, and 1 <= b,c <= 9, so subtract 1 from each to start at 0, which reduces 12 - 3 = 9, and 14 - 3 = 11. That's why you look at powers of x^9 and x^11 instead of x^12 and x^14. Since b and c have the same constraints, that's why the second term in the generating function is squared, while the term (1 + x + x^2 + x^3) represents your first constraint a.

Moving to Computer Science, as well.
Was This Post Helpful? 0
  • +
  • -

#3 xilith117  Icon User is offline

  • D.I.C Head

Reputation: 3
  • View blog
  • Posts: 99
  • Joined: 13-August 11

Re: I need to figure out the number of possible combinations

Posted 10 February 2014 - 10:47 PM

*whooosh* you lost me. Big time. Sorry.
Was This Post Helpful? 0
  • +
  • -

#4 macosxnerd101  Icon User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12147
  • View blog
  • Posts: 45,157
  • Joined: 27-December 08

Re: I need to figure out the number of possible combinations

Posted 10 February 2014 - 11:11 PM

A generating function is a nice way to use a geometric series to count things, where the exponent i of x^i is the quantity we are counting. So x^3 means there are three objects, and the coefficient is the number of ways you get three elements as combinations.

Do you understand how I set up the Diophantine equation to model your constraints? What about how I set up the generating function? The easy way out is to plug the generating function into Wolfram Alpha, hit expand, then just add up the coefficients of x^9 and x^11. Multiply that number by 25 (by your first term of 25 possible first characters) to get your answer.
Was This Post Helpful? 0
  • +
  • -

#5 mojo666  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 408
  • View blog
  • Posts: 882
  • Joined: 27-June 09

Re: I need to figure out the number of possible combinations

Posted 11 February 2014 - 12:32 AM

Quote

so 25x4x9x9 = 8100 WOULD be my answer but there is one more rule to this code that complicates it.
The second Char + the First third char + the fifth char must equal either 12 or 14. I do not know how to calculate the number of combinations taking this into consideration.


The problem is simple enough where you can somewhat brute force this without having to resort to complicated math. If it was a much more convoluted problem, the complicated math greatly simplifies things.
We have 4 possible values for the 2nd number, which effects what value the other 2 numbers can add up to.
a = Number of ways 3rd and 5th add up to 11 or 13
b = Number of ways 3rd and 5th add up to 10 or 12
c = Number of ways 3rd and 5th add up to 9 or 11
d = Number of ways 3rd and 5th add up to 8 or 10

So your answer would be 25*(a + b + c + d)

"a" represents when the 2nd number is 1, so now you can just show the possible pairs of 3rd and 5th

2 9
3 8
4 7/9
5 6/8
6 5/7
7 4/6
8 3/5
9 2/4

So, there are 14 ways the 3rd and 5th number add up to 11 or 13. Instead of listing you can identify the first number that has a single corresponding pair and the first number that has 2 corresponding pairs. In the above example they are 2 and 4 respectively, so a = 1*(4-2) + 2*(9-4) = 14. Which ever method you chose, just do the same for b, c, and d then plug the results into the equation.
Was This Post Helpful? 1
  • +
  • -

#6 xilith117  Icon User is offline

  • D.I.C Head

Reputation: 3
  • View blog
  • Posts: 99
  • Joined: 13-August 11

Re: I need to figure out the number of possible combinations

Posted 11 February 2014 - 10:39 PM

that seems much simpler
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1