Wikipedia:Reference desk/Archives/Mathematics/2007 January 9

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

January 9

Reversible Gas Turbines

Question moved to the Science reference desk.  --Lambiam^Talk 21:55, 9 January 2007 (UTC)

Generating permutations

I refer to this section of the Permutation article:

BEGIN

Algorithm to generate permutations

For every number $k$ ($0\leq k<n!$) this following algorithm generates the corresponding permutation of the initial sequence $\left(s_{j}\right)_{j=1}^{n}$:

 function permutation(k, s) {
     var int factorial:= 1;
     for j = 2  to length(s) {
        factorial := factorial* (j-1);
        swap( s[j - ((k / factorial) mod j)], s[j]);
     }
     return s;
 }

Notation

• k / j denotes integer division of k by j without rest, and
• k mod j is the remaining rest of the integer division of k by j.

END

The algorithm is supposed to generate every different permutation of the integers 1 to n, but when I coded it there were repetitions - could someone else check this, please?

Also, the bit following "Notation" seems to be written very clumsily, omitting the generally-understood word "remainder".81.153.219.51 16:42, 9 January 2007 (UTC)

I don't claim I understand why the algorithm does what it does, but I've checked all n! outputs for sequence length n up to and including 9, and it is working just fine for me. Are you perhaps using the permuted s as input to a next call?

As to the clumsiness, I'd say: {{sofixit}}. If you don't feel comfortable doing that (but why wouldn't you?), consider leaving a comment on the article's talk page.  --Lambiam^Talk 21:47, 9 January 2007 (UTC)

Yes, I was using successive sequences - when I reset to 123...n order before each use, everything worked fine, thanks. With this apparently not working I searched for alternative algorithms - this one seems by far the shortest. It's a pity there is no attribution of source.

Re. the text, yes I'll change it - I hadn't fully appreciated how things were here.

With a dynamic IP address it may not look as if I'm the same person as before, but I am.81.153.220.80 18:27, 10 January 2007 (UTC)

recurrence relation

can someone explain what a recurrence relation is and how it works in simple terms, giving an example. i have read the wiki and dont understand it. thanks —The preceding unsigned comment was added by 86.136.40.7 (talk) 23:00, 9 January 2007 (UTC).

If you have a sequence x₀, x₁, x₂, x₃, ..., and from some point on in the sequence each next value x_n+1 can be expressed as a function of the earlier elements x_n, x_n−1, ..., so

x_n+1 = f(x_n, x_n−1, ...)

for some function f, we say that the sequence satisfies a recurrence relation (namely the equation just given).

A very simple example is:

x₀ = 0,

x_n+1 = x_n + 1.

This gives the sequence 0, 1, 2, 3, ... , since 1 = 0 + 1, 2 = 1 + 1, 3 = 2 + 1, and so on. Slightly more complicated:

x₀ = 1,

x_n+1 = 2x_n.

Here the sequence is 1, 2, 4, 8, ... . A well-known sequence is this one:

x₀ = 0,

x₁ = 1,

x_n+1 = x_n + x_n−1.

The sequence you get is 0, 1, 1, 2, 3, ... , since 1 = 1 + 0, 2 = 1 + 1, 3 = 2 + 1, and so on. Each next value in the sequence is the sum of the last two before it. This sequence is known as the Fibonacci sequence. Now try this one yourself:

x₀ = 0,

x₁ = 1,

x_n+1 = 2x_n − x_n−1 + 2.

 --Lambiam^Talk 00:14, 10 January 2007 (UTC)

Coincidentally, I mentioned another example a few questions ago: the recurrence relation for Chebyshev polynomials. Whereas Lambiam's sequences are just integers, this sequence consists of polynomials, the T_{n. --KSmrq^T 05:28, 10 January 2007 (UTC)}