[quote user="ammoQ"][quote user="CodeRage"][quote user="ammoQ"]
What you are trying to do is to find all possible ways to divide your pool (which has to have an even number of elements) into pairs.
A bit of math tells you that there are for n elements in your set, your program has to consider n!/((n/2)! * 2^(n/2)) possible arrangements.
Note that this number is larger than (n/2-1)!2^(n/2-1); for a set of 1000 elements, this means it's larger then 499!2^499.
I'm afraid no algorithm, no matter how clever, will finish that till the end of the universe.
[/quote]
Actually, it seems he is trying to generate a NxN matrix, filled with numbers 1 through N, where no number appears in the same row or column more than once. The algorithm I gave seems to work for powers of two, and I wrote it without a whole lot of thought and didn't spend much time at it, and my test cases 4 and 8 worked. This is basically a matrix of a round robin schedule, where the first column represents the player number, columns 2-N represent each round, where the data gives the
I am sure there is a fairly efficient and systematic way of generating such a matrix. Anyway, I tried, and don't have much more time to think about this...
[/quote] Aahh yes, I see your point.
I think the real task is: "Find all possible pairs. (The number of possibe pairs is n(n-1); add an index column and you get a nice nn matrix). Show them in a matrix where the first columns is 1..n and the other columns show some arrangements of those pairs, so that no number appears twice in the same row or column and some kind of symmetry takes place: If the value in the row n is x, then the value in row x shall be n.
Anyway, I don't see a legitimate use for that in any real world problem. For a brute force optimization, the n!/((n/2)! * 2^(n/2)) method is the way to go.
Note that though your algorithm produces valid results (by the specification above), there are other, valid results too.
For example, for n=6, your algorithm produces:
1 6 5 4 3 2
2 5 3 6 4 1
3 4 2 5 1 6
4 3 6 1 2 5
5 2 1 3 6 4
6 1 4 2 5 3
Another possible correct result would be:
1 6 5 4 3 2
2 4 6 3 5 1
3 5 4 2 1 6
4 2 3 1 6 5
5 3 1 6 2 4
6 1 2 5 4 3
i A B C D E
This result is significantly different from your result; you cannot simply get it by permuting the columns of your result. To see the significance of the difference, let's pretend that all numbers represent persons; 1 loves 6, 2 loves 4 and 3 loves 5. All other combinations are hate. Let's say love scores +1 and hate -1.
The score of column A is 3, while B,C,D and E have a score of -3. In your matrix, columns A, C and D have a score of -1, B and E have -3.
In other words, the method implemented in your algorithm is not sufficient to find the optimal result (which is what the OP is looking for, I assume), if only the score of whole columns is considered. This is not a fault in your algorithm (which is really well done!), it's a flaw in the original specification.
[/quote]
The real world use is to generate a schedule for a round-robin style tournament. The matrix shows which players compete each round. You can easily see why each number can only appear once in each row, and once in each column (a player can't play in two games in the same round, and no player should face the same opponent more than once). Also note that if player N competes with player M in a round, the matrix shows player N competing with M in the same round.
| Opponent |
Player# | Round 1 | Round 2 | Round 3 | Round 4 | Round 5 |
1 | 6 | 5 | 4 | 3 | 2 |
|
2 | 5 | 3 | 6 | 4 | 1 |
|
3 | 4 | 2 | 5 | 1 | 6 |
|
4 | 3 | 6 | 1 | 2 | 5 |
|
5 | 2 | 1 | 3 | 6 | 4 |
|
6 | 1 | 4 | 2 | 5 | 3 |
|
There are many other matrices that solve this problem, but I don't see why any particular matrix would be better than another given this usage. (Of course I'm not 100% certain this is the usage the original poster had in mind)