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 |
|
|
|