10 Replies Latest reply: Aug 9, 2007 5:52 PM by 807605

# help with algorithm about distrbuting numbers in a matrix

Hi,

I have to do the following:

I need to distribute N numbers in a (Y,N) matrix. The only problem is that each number should be unique on its row and its column (sth like sudoku). Number N is always the same as the columns.

For example in a simple situation where there are 3 rows and 3 columns I should distribute 1, 2 and 3 like this (in rows): 1,2,3 - 2,3,1 - 3,1,2

Rows should always be less than or equal number of columns.

Any help would be appreciated.
• ###### 2. Re: help with algorithm about distrbuting numbers in a matrix
erm... how to do it?
• ###### 3. Re: help with algorithm about distrbuting numbers in a matrix
For an N size row there are N! different unique permutations.
N! = N * (N-1) * (N-2) * ... * 1

So for 3 there are 3*2*1=6 combinations
123, 132, 213, 231, 312, 321

Pick out a combination for every row.
Find a way to map a number to a specific permutation.
When you get a random number from 1 to 6 make sure not to
pick the same number twice.
• ###### 4. Re: help with algorithm about distrbuting numbers in a matrix
But if you pick 123, 132 and 321:
```123
132
321```
The first two columns violate the uniqueness requirement.
• ###### 5. Re: help with algorithm about distrbuting numbers in a matrix
Here's my go: no claim how good it is.
Start off with the matrix filled with a basic rotation:
```12345
23451
34512
45123
51234```
Then shuffle. Repeatedly:
1. Randomly choose to swap rows or cols.
2. Randomly pick a pair of rows/cols. Swap them.
For example, swapping the first and last row on
the original matrix yields:
```51234
23451
34512
45123
12345```
• ###### 6. Re: help with algorithm about distrbuting numbers in a matrix
Here's my go: no claim how good it is.
Start off with the matrix filled with a basic
rotation:
```12345
23451
34512
45123
51234```
Then shuffle. Repeatedly:
1. Randomly choose to swap rows or cols.
2. Randomly pick a pair of rows/cols. Swap them.
For example, swapping the first and last row on
the original matrix yields:
```51234
23451
34512
45123
12345```
this sounds nice and easy. At the moment I am trying to do the following (which I am sure is bad) : a while (true) loop that picks a random number and random place and checks horizontally and vertically if it is ok to put the number in the randomly chosen place if not then another place is chosen. This is really time consuming though.
• ###### 7. Re: help with algorithm about distrbuting numbers in a matrix
Here's my go: no claim how good it is.
Start off with the matrix filled with a basic
rotation:
```12345
23451
34512
45123
51234```
You don't need to go any farther. That IS a solution already. And the OP hasn't indicated that more than one solution is a requirement.

Clearly finding all solutions is computationally intractable, so by the zero-one-infinity rule, the requirement must be to find one solution.
• ###### 8. Re: help with algorithm about distrbuting numbers in a matrix
I just noticed that the solution above has a problem when columns are less than the number of rows. In my algorithm it is important that N (which represents the maximum allowed number i.e. if N=3 then I can only insert 1, 2, 3) should be equal to the number of columns but rows can be greater or equal to N. So if N is 2 (and consequently the columns are also 2) I get this:

1 2
2 1
1 2

in the cyclic insertion. I guess if N is 10 and rows are 15 then I will get even more "errors" that would be hard to resolve with the random insertion later on.
• ###### 9. Re: help with algorithm about distrbuting numbers in a matrix
Um, you shouldnt fail to apply common sense.
It should be obvious that N = max(row count, column count)

or... given this "requirement":
"Number N is always the same as the columns."

assert column count <= row count
• ###### 10. Re: help with algorithm about distrbuting numbers in a matrix
Apply commonsense? Isn't the default value true? Silly me -- it's false.