# nxn 0-1 array enumeration

• 10-16-2009, 07:24 AM
hollygrove
nxn 0-1 array enumeration
Hi. I am have trouble trying to create a code the will completely enumerate an array of square dimension. For instance, if I have an int[][] array, I would like the entries of the array to be only 0's and 1's with each column and row having a total summation of 1. So again if I declare an array: int[][] thisArray = new int[3][3]; I would like to be able to obtain the following 3!=6 arrays.

[1][0][0] [0][1][0] [0][0][1]
[0][1][0] [1][0][0] [0][1][0]
[0][0][1] [0][0][1] [1][0][0]

[1][0][0] [0][0][1] [0][1][0]
[0][0][1] [1][0][0] [0][0][1]
[0][1][0] [0][1][0] [1][0][0]
• 10-16-2009, 07:42 AM
pbrockway2
How did you know there were 6 such 3x3 arrays? And how did you figure out what they were?

I ask because step 0 of writing your code will be to figure out the algorithm. Basically this means writing down the steps you followed in such a way that the steps

(1) are comprehensive: ie leave nothing out
and
(2) are really simple

At that point you can start writing some code.
• 10-16-2009, 08:19 AM
hollygrove
I am starting with a number of items such as persons 1, 2, and 3. Therefore I have a total person count of 3. I also have another number of items, say events 1, 2, and 3, that will always have the same count as persons. So if there are 2 persons then there are 2 events. Now, say one person can visit only one event at a time, and each event can host only a single person. So if person 1 visits event 2, then I need array entry [1][2] = 1. Array entries of 0 mean the person does not visit the event. Now I would like to consider all possible combinations of persons to events. Therefore, if there are 3 persons and 3 events, then there are 3!=6 possible array scenarios. That is how I arrived at the 6 six arrays. If there were 2 persons and 2 events, then there would be 2!=4 arrays and so on.
• 10-16-2009, 09:33 AM
pbrockway2
Quote:

Now I would like to consider all possible combinations of persons to events.
OK. So imagine that the events were being held in separate rooms along a corridor. The association of people to events would, effectively, be an ordering of the people and you would get one matrix per ordering. Such orderings are known as permutations.

My earlier remark stands: to develop a algorithm to enumerate permutations you have to make precise the very thought processes you went through both to determine that there are 3! permutations of three elements and, indeed, to write them out as you did in your original post.

If you just want such a permutation enumeration algorithm (rather than want the joy of discovering one) then Google will turn up any number: including this Wikipedia article on Numbering Permutations.