Example: How many five-letter words can be made from the letters: STATE MEET

Usually what I'd do is bash out all of the cases, but it's too slow for a speed test, and I wanted to see if I could create a program on the calculator.

The way to do it is probably through generating functions, but I don't know if that is possible on the TI-84+ CE calculator. We also have a TI-89, which can handle the advanced computations, but I have less experience with it.

Here's a link to an in-depth explanation of another example problem: https://math.stackexchange.com/questions/20238/6-letter-permutations-in-mississippi

Thanks so much for the help! Very Happy
Just running mathematical computations, the 89 is vastly faster and has support for much more than the 84+ (ex. 84+ accepts scientific notation values up to 99 and the 89 supporst values up to 999).

The 89 also has more advanced string operations than the 84+, so I'd say that the 89 would be the ideal candidate. I actually need to learn more about the 89's string operations myself. Razz

Maybe this can be a learning experience with the 89 for me too Very Happy
Are you trying to calculate the number of permutations or are you looking for a program that spits out all the combinations?
Also, this type of problem is completely doable on both the CE and the ti-89.
mr womp womp wrote:
Are you trying to calculate the number of permutations or are you looking for a program that spits out all the combinations?
Also, this type of problem is completely doable on both the CE and the ti-89.


I’m trying to find just the number of permutations. How do you go about programming this on the CE?
noobcake01 wrote:
mr womp womp wrote:
Are you trying to calculate the number of permutations or are you looking for a program that spits out all the combinations?
Also, this type of problem is completely doable on both the CE and the ti-89.


I’m trying to find just the number of permutations. How do you go about programming this on the CE?


Ah, ok. I thought you were talking about listing permutations.
Do they have to be real words in a specific language? Or just combinations of letters?
tr1p1ea wrote:
Do they have to be real words in a specific language? Or just combinations of letters?


not real English words, just permutations of letters
OK and do you need the actual permutations or do you just need to know 'how many' permutations exist?
tr1p1ea wrote:
OK and do you need the actual permutations or do you just need to know 'how many' permutations exist?


Just the number of permutations!
I came up with a solution for this in 84+(CE) Basic. Note that if you have multiple words they must be entered without spaces.

Code:
Input "WORD=?",Str1
Prompt N
Delvar L₃length(Str1→dim(L₃
For(I,1,Ans
inString(Str1,sub(Str1,I,1
1+L₃(Ans→L₃(Ans
End
{N!→L₁
For(I,1,dim(L₃
Ans→L₂
For(J,1,L₃(I
augment({0},L₂/J→L₂
Ans+augment(L₁,{0→L₁
End
End
Ans(N+1


Perhaps out of habit I wrote this in an almost obfuscatedly optimized way, but let's break down what's going on here.

First, I delete L₃ and set its size to the length of the word (this ensures it is initialized to all zeros). This list will be used to accumulate the frequency of each letter.

Code:
Delvar L₃length(Str1→dim(L₃


Next, loop I from 1 to the length of the string (which is in Ans from the previous line).

Code:
For(I,1,Ans


Now, find the index of the first occurence of the I-th letter in the word. This effectively maps each distinct letter to a unique integer.

Code:
inString(Str1,sub(Str1,I,1


Now that we have the mapped index, increment the corresponding element of L₃, and loop to the next letter.

Code:
1+L₃(Ans→L₃(Ans
End


At this point, each non-zero element of L₃ holds a letter frequency. For example, in the case of STATEMEET, it would be {1,3,1,0,3,1,0,0,0}.

Now, we'll use lists to represent polynomials for the generating function approach. Index 1 of a list will be the constant term, index 2 will be the coefficient of x, index 3 will be the coefficient of x², and so on.

We start with the polynomial (which we'll call P) with N! as a constant term in L₁.

Code:
{N!→L₁


Now, we loop over each letter frequency to multiply its corresponding generating polynomial.

Code:
For(I,1,dim(L₃


Here, we initialize L₂ to P (which is in Ans) times x^0 / 0! (that is, the constant term of 1 present in each generating polynomial).

Code:
Ans→L₂


Now, we loop J from 1 to the current letter frequency to add in P times x^J / J!. (This loop is implicitly skipped for any 0-frequency element of L₃.)

Code:
For(J,1,L₃(I


At the moment, L₂ is P times x^(J-1) / (J-1)!. To transform this into P times x^J / J!, we prepend a 0 (effectively multiplying by x) and divide by J.

Code:
augment({0},L₂/J→L₂


Here, we add the resulting polynomial to L₁ (to which we append a 0 so the number of list elements match), and loop to the next exponent.

Code:
Ans+augment(L₁,{0→L₁
End


Now L₁ (and Ans) is the new value of P, so loop to the next letter frequency.

Code:
End


Finally, we extract the coefficient of x^N from the resulting polynomial.

Code:
Ans(N+1


Let me know if you have any questions!
Thanks so much calc84maniac! I definitely would not have come up with this

However, the calculator is not allowing me to do
DelvarL3length(Str1–>L3

citing “ERROR: DATA TYPE”

Is it just user error on my side?
You should store it to ʟ3(1 which is an element number. You can;t store a number into a list itself, the number has to be in an element of the list
noobcake01 wrote:
Thanks so much calc84maniac! I definitely would not have come up with this

However, the calculator is not allowing me to do
DelvarL3length(Str1–>L3

citing “ERROR: DATA TYPE”

Is it just user error on my side?


Oh, sorry, that was supposed to be →dim(L₃. I'll go update my post.
calc84maniac wrote:
noobcake01 wrote:
Thanks so much calc84maniac! I definitely would not have come up with this

However, the calculator is not allowing me to do
DelvarL3length(Str1–>L3

citing “ERROR: DATA TYPE”

Is it just user error on my side?


Oh, sorry, that was supposed to be →dim(L₃. I'll go update my post.


YOU. ARE. AWESOME.

Thank you so much!
  
Register to Join the Conversation
Have your own thoughts to add to this or any other topic? Want to ask a question, offer a suggestion, share your own programs and projects, upload a file to the file archives, get help with calculator and computer programming, or simply chat with like-minded coders and tech and calculator enthusiasts via the site-wide AJAX SAX widget? Registration for a free Cemetech account only takes a minute.

» Go to Registration page
Page 1 of 1
» All times are UTC - 5 Hours
 
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum

 

Advertisement