Login [Register]
Don't have an account? Register now to chat, post, use our tools, and much more.
This is an archived, read-only copy of the United-TI subforum , including posts and topic from May 2003 to April 2012. If you would like to discuss any of the topics in this forum, you can visit Cemetech's TI-BASIC subforum. Some of these topics may also be directly-linked to active Cemetech topics. If you are a Cemetech member with a linked United-TI account, you can link United-TI topics here with your current Cemetech topics.

This forum is locked: you cannot post, reply to, or edit topics. TI-Basic Brain Teasers => TI-BASIC
Author Message
Zaphod Beeblebrox


Member


Joined: 02 Jul 2007
Posts: 119

Posted: 06 Jun 2010 12:23:33 pm    Post subject:

Given a permutation of numbers in L1 (e.g. {1,5,4,2,3} or {3,5,7,4,2,6,1}), determine the number of cycles in that permutation. For example, in the permutation (1 5 4 2 3), the 2 cycles are (1) and (5 3 4 2). In the permutation (3 5 7 4 2 6 1), the 4 cycles are (3,7,1), (5,2), (4), and (6). The goal of the program is to determine the number of cycles, not determine what the cycles are.

Here is my solution. (111 bytes, without the program name letters)
[spoiler]0->C
For(Z,1,dim(L1
If L1(Z
Then
C+1->C
Z->A
ClrList L2
Repeat L1(Z)=L1(A
L1(A->L2(1+dim(L2
L1(A->A
End
For(A,1,dim(L2
(L1!=L2(A))L1->L1
End:End:End
C
[/spoiler]


Last edited by Guest on 06 Jun 2010 12:24:09 pm; edited 1 time in total
Back to top
Weregoose
Authentic INTJ


Super Elite (Last Title)


Joined: 25 Nov 2004
Posts: 3976

Posted: 07 Jun 2010 05:05:41 pm    Post subject:

Little-used trick: L1√(L1≠L2(A

Not knowing permutation cycles, I went down one path and then came back with a routine for the Stirling numbers of the first kind. Oops.
Back to top
Zaphod Beeblebrox


Member


Joined: 02 Jul 2007
Posts: 119

Posted: 08 Jun 2010 08:09:33 pm    Post subject:

Oh, sorry, I probably should have explained what a cycle in a permutation is. Consider the following permutation on seven numbers:

(1 2 3 4 5 6 7)
(3 2 4 7 6 5 1)

The first cycle can be found by looking at the first element, 3. That is the first number in our cycle. We now go to that number element, the third element, which is 4, we go to that fourth element which is 7, we go to the seventh element, which is 1. Now were back to the first element, which is where we started. Thus, the first cycle is (3,4,7,1). The next cycle starts at the second element, which is 2. We go to the second element, which is where we started, so we are done; the cycle is just (2). The third cycle starts at the fifth element, which is 6. We go to the 6th element which is 5, so we're back to the fifth element, where we started, thus the cycle is (6,5). By this reasoning, the above permutation has 3 cycles: (3,4,7,1), (2), and (6,5). Hopefully this makes some modicum of sense.

Edit: Thanks for the optimization. Two bytes saved!


Last edited by Guest on 08 Jun 2010 08:12:00 pm; edited 1 time in total
Back to top
Weregoose
Authentic INTJ


Super Elite (Last Title)


Joined: 25 Nov 2004
Posts: 3976

Posted: 09 Jun 2010 03:10:05 am    Post subject:

Gotcha.

This'll have to do until I can get new batteries and not have my calculator keep shutting off on me. (58 bytes)

[spoiler]DelVar AWhile max(L1
max(L1→B
While L1(Ans
L1(Ans→C
0→L1(B
C→B
End
A+1→A
End
Ans[/spoiler]
Back to top
thornahawk
μολών λαβέ


Active Member


Joined: 27 Mar 2005
Posts: 569

Posted: 09 Jun 2010 08:08:07 am    Post subject:

Maybe you can post the Stirling number routine anyway in a separate post? :)

thornahawk
Back to top
Weregoose
Authentic INTJ


Super Elite (Last Title)


Joined: 25 Nov 2004
Posts: 3976

Posted: 09 Jun 2010 02:27:13 pm    Post subject:

(2) and (21) give:

DelVar XFor(K,0,N-M
K+N-M
X+(-1)^K(Ans+M-1) nCr Ans(2N-M) nCr (Ans-2K)/K!sum(seq((-1)^IK nCr I(K-I)^Ans,I,0,K→X
End
Ans(M≤N

The accuracy is spotty for large N, but that's to be expected when dealing with big factorials. It also crashes when N=M (00), and the (M≤N) from the last line is there to reset to zero what would otherwise output as M. In terms of ingenuity, I would not rate this one highly.


Last edited by Guest on 09 Jun 2010 02:28:35 pm; edited 1 time in total
Back to top
Display posts from previous:   
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
    »
» View previous topic :: View next topic  
Page 1 of 1 » All times are GMT - 5 Hours

 

Advertisement