Permutation Cycles

[Zaphod Beeblebrox]

Given a permutation of numbers in L₁ (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]

[Weregoose]

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.

[Zaphod Beeblebrox]

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!

[Weregoose]

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]

[thornahawk]

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

thornahawk

[Weregoose]

(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 (0⁰), 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.