Uhhmm... I need ideas and possibly help here... ...a bit advanced
(It shouldn't be extremely hard for Programmers with good taste of badass algorithm(s))
Any help or ideas would be appreciated.


I am stuck in implementing permutations of mutually exclusive columns of an arbitrary matrix...
Where a column is only used once and only once....

This is a real trivial problem, break it down into a graph problem
...though, I could break it down to trees and use Kruskal's MST algorithm to find the minimum permutation... but I don't think thats fine for the fact that based on my intuition, I did get (n^2 *(n!)) computation time! which is unrealistic for larger matrices

Lemme use a real small example to illustrate my problems

I have a 3x3 matrix
I need to pick n elements, where {0 <= n <= rows}.. example if n is 3...

|  3  5  2 |
|  2  9  8 |
|  1  7  3 |

my permutations will be... n! = 3! = 6
(Remember, for any permutation, NO column or row may be selected more than once)
(3, 9, 3), (3, 8, 7)
(5, 2, 3), (5, 8, 1)
(2, 2, 7), (2, 9, 1)
...and in this case, the smallest permutation is (5, 2, 3)... i.e the permutation whose maximum unit..(in this case, its 5) is the minimum possible time to finish in all of the permutation.
Application: cluster computing..., Natural Language Processing...

Can you help me ideas?
I have a 4x4 matrix for more illustration . . .

|  3  5  2  9  |
|  2  9  8  4  |
|  1  7  3  8  |
|  8  4  5  3  |

I need to pick n elements, where {0 <= n <= colums}.. example if n is 4...
my permutations will be 4! = 24
(3, 9, 3, 3), (3, 9, 8, 3), (3, 8, 7, 3), (3, 8, 8, 3), (3, 4, 7, 5), (3, 4, 3, 7)
(5, 2, 3, 3), (5, 2, 8, 3), (5, ....etc
...etc

A Math student suggested a Mathematical approach... Eigen Vectors? Is it realistic to think of researching that --can't think of any approach apart from a discrete one. ...My undergraduate degree field isn't so much of the Mathematics or Computing I love..

SIDE NOTE: only the smallest permutation is needed... the matrix may reach 100*12...
Once again, Any help or ideas would be appreciated.
Thanks in advance... WhiZTiM.. (Timothy)

WhiZTiM: Uhhmm... I need ideas and possibly help here... ...a bit advanced
(It shouldn't be extremely hard for Programmers with good taste of badass algorithm(s))
Any help or ideas would be appreciated.


I am stuck in implementing column restricted permutations of an arbitrary matrix...
Where a column is only used once and only once....

This is a real trivial problem, break it down into a graph problem
I have a 3x3 matrix
I need to pick n elements, where {0 <= n <= rows}.. example if n is 3...

|  3  5  2 |
|  2  9  8 |
|  1  7  3 |

my permutations will be... n! = 3! = 6
(Remember, for any permutation, NO column or row may be selected more than once)
(3, 9, 3), (3, 8, 7)
(5, 2, 3), (5, 8, 1)
(2, 2, 7), (2, 9, 1)
WhiZTiM.. (Timothy)

in this example, your results are not column restricted. they seem randomly picked. I do not see (5, 8, 1) being in the same column or am I missing the point?

lordZOUGA:
in this example, your results are not column restricted. they seem randomly picked. I do not see (5, 8, 1) being in the same column or am I missing the point?

Yeap... you are missing a point...
NO column may be repeated! you may only select from a column once. i.e all entries must be mutually exclusive (column wise).

WhiZTiM:
Yeap... you are missing a point...
NO column may be repeated! you may only select from a column once. i.e all entries must be mutually exclusive (column wise).

oh.. couldn't reply sooner, my internet service started acting all weird.

is this part of that rat related problem we talked about? if so, can you post the original problem?

are there no constraints? like highest possible number in each box or highest possible sum of a column?

I was thinking that if selections were column restricted(like you can only select whole columns) then you can use a graph to solve this..

lordZOUGA:
oh.. couldn't reply sooner, my internet service started acting all weird.

is this part of that rat related problem we talked about? if so, can you post the original problem?

are there no constraints? like highest possible number in each box or highest possible sum of a column?

I was thinking that if selections were column restricted(like you can only select whole columns) then you can use a graph to solve this..

^its rabbits. Yeah.
Its pretty simple to understand...
In better English, all elements in each permutation are mutually exclusive row-wise and column-wise. For example, for a permutation, once I pick an element A21 in matrix A, there must be no other element Ai1 and Aj2 in that permutation... Where i and j are row and column number rspctvly.
...just like the example I cited in the top post.

My problem is implementation...

Graph?
I dnt really think so.
Except if u have a few pointers on how I should generate my graph tree effectively enforcing those rules, else I did have to generate the tree of one of them by brute force...

And I think thats unrealistic for larger matrix.
They are constraints..