Cyclic permutations

Problem: How many permutations of N objects that have the structure of one big cycle are there? Give a method to generate all of them. I have started thinking about this after reading the "runaround numbers" problem at USACO. A runround number must use (decimal) digits at most once and steping thru them starting at any digit should lead to steping thru all digits. A step is a transition from digit i to digit j done like this: (1) read digit in position i, (2) go to the right that many digits, the digit to the right of the rightmost digit is the leftmost digit, (3) you have just arived at position j. This example is from the USACO problem statement. Consider the number 81362. Let's start at the middle digit (that is, 3). After a step we reach 8. After another step we reach 6. Then, in order, 2, 1, 3. We have arrived from where we started and in the process we visited all the digits. A number that is not a runaround number is 1234. If we start at 2 the steping sequence is: 2, 4, 4, 4, .... Digits 1 and 3 are never visited. Notice that a runaround number is a way of describing a "big cycle permutation" of at most 9 elements (numerotation system base minus one: the digit "zero" can never be part of a runaround number). We should notice that using runaround numbers we can give multiple representations for the same big cycle permutation. For example the numbers 81362 and 81367 represent the same big cycle permutation. Nevertheless counting big cycle permutations and generating them is intimately related to the USACO training problem. In order to answer the question we can start by finding a better representation for big cycle permutations. There is a standard way to do this. First let us number the digit positions: 43210. Then, we can see that visiting the runaround number 81362 starting from 3 visits the digits in positions (2, 4, 1, 0, 3). If we would have started at digit 8 then the visited positions would have been (4, 1, 0, 3, 2). In this later representation it is easier to see all the equivalent representations of the same big cycle permutation: two representations are equivalent if they can be obtained from one another thru rotation. It is the same thing as saying that it does't really matter from where we start visiting the runaround number. We can see clearly now how many big cycle permutations are there. The representation we used is in itself a permutation of N elements. But two different permutations of N elements represent the same big cycle permutation of N elemens if they can be obtained from one another thru rotation. In a rotation equivalence class there are always N elements. Wrapping it up we find that there are N!/N = (N-1)! big cycle permutations. How to generate them? Well, first we need to generate one representant of each equivalence class (defined by rotation). We can choose to generate the representant that ends with the biggest number: in the example above we would generate only 5-permutations that end in with 4. Doing this is easy. Just generate all permutations of {0, 1, ..., N-2} and append (N-1) at the end. In order to generate all permutations of {0, 1, ..., N-2} we can use any "standard" method. One good approach is to reach for The Art of Computer Programming by Knuth and find the answer there. If we use C++ then we can cheat :) and use next_permutation function from the header. This is a trivial problem but for some reason I found it interesting. I have posted it here only because there was no entry in a long time. NOTE: "big cycle permutation" is not standard terminology as far as I know.