Derangement or what? [closed]

Closed. This question is off-topic. It is not currently accepting answers.

---

Want to improve this question? Update the question so it's on-topic for Stack Overflow.

Closed 12 years ago.

开发者_C百科 Improve this question

I was looking at the description of a derangement that states "a derangement is a permutation of the elements of a set such that none of the elements appear in their original position". But then it gave 9 derangements for a set of 4 items. That doesn't make sense to me, because I only get 4 discrete sets from 4 items.

For example:

1234 3142 2413 4321

Is there a different term than derangement for sets where the numbers don't have the same order as in any other set, based on a particular number of items?

And does anyone know of an algorithm for generating the derangements?

---

The nine derangements are:

2143
2341
2413
3142
3412
3421
4123
4312
4321

As you can see, column 1 does not contain 1, column 2 does not contain 2 and so on. In addition, every row has the numbers 1, 2, 3 and 4 and there are no duplicates (they're sorted to make that easier to detect).

---

For what it's worth, that was discovered with a brute force attack (the attack space was relatively small):

#include <stdio.h>

int main (void) {
    int a, b, c, d, skip;

    for (a = 1; a <= 4; a++) {
        for (b = 1; b <= 4; b++) {
            for (c = 1; c <= 4; c++) {
                for (d = 1; d <= 4; d++) {
                    skip  = (a==1) || (b==2) || (c==3) || (d==4);
                    skip |= (a==b) || (a==c) || (a==d);
                    skip |= (b==c) || (b==d);
                    skip |= (c==d);
                    if (!skip) {
                        printf ("%d%d%d%d\n", a, b, c, d);
                    }
                }
            }
        }
    }
    return 0;
}

---

It turned out that I was looking for a complete latin square (row-complete and or column-complete). I had already coded an algorithm to detect those, but didn't know if this kind of thing had a name. That's it, thanks.