Thread: Support Needed - Populating a 2d matrix with different binary number representations.

Hello everyone,
I am trying to write a function that does the following:
When given int n and int k, it will:


E.G.
Given n=2 and k=1, the function will create a matrix for the following cases:
00
01

00
10

01
00

10
00

I do not expect someone to write this code for me. I would appreciate some direction though on how to go about it as I can only come up with a way to create some combinations but not all.
Thank you in advance,
Java Beginner.

Q:"What code do you have so far?"
A:I have a working function that when given a 2d matrix representing a binary number, will increment it to the next larger number with the same number of bits valued 1.
A:I have a working function that when given a 2d matrix representing a binary number, will increment it to the next larger number with any number of bits valued 1.

Q:"What is a "place"? One of the slots in the array?"
A:Yes, one of the slots in the 2d matrix.

Q:"Do the slots in the array hold a single bit with a value 0 or 1?"
A:Yes. As the matrix represents a binary number with K 1's, every slot in the 2d matrix will hold a single bit with a value 0 or 1, where the number of slots with bit value 1 equals K.

Q:"How would 01101 be stored in a 2D array?"
A: This number is equal to 000001101 and would be presented by a 2d matrix NxN, where n=3, k=3:
000
001
101



Valid Example:
For N=6, K=9, Matrix Size 6x6, I will need to present all different binary numbers with 6x6 bits, of which only K bits are valued 1 and the rest are valued 0.
E.G. The number 000000000000000000000111000000111111

Or
000000
000000
000000
000111
000000
111111

Is one permutation for N=6.

I would like to find a way that finds all permutations for any given N, always keeping of course K=(NxN)\4 as the number of bits valued 1 in every permutation.

Q:"Why a 2D array?"
A:The matrix represents a possible board and therefore must be 2d.

Q:"What problems are you having? Do you have the algorithm for generating the binary numbers?"
I have an algorithm that could generate all possible binaries for NxN matrix. However, it does it regardless of keeping the same number of bits valued 1 in every permutation.
For n=6, any binary 6x6 bits long with more or less than K=(NxN)\4=9 bits valued 1 in is invalid. I need only those with K 1's, not all.

I realized I can generate a matrix NxN representing every binary with NxN bits (regardless of K). Then I can count the number of bits valued 1 in that matrix and test if it equals K. If so, this permutation is valid. However, this is very inefficient. There must be a better way. I don't want to generate so many different binaries I don't need(ones that contain more or less than K bits valued 1).

Is there no other way?
The word of a seasoned programmer would be enough for me to settle for the above mentioned solution and stop trying something more efficient.
Thank you.

Now was an hour ago. Later is now. I would like to improve it. But hey, I just don't know how.
My thanks for the correspondence tho, I did made me realize at least one possible solution, inefficient as it may be.

Originally Posted by Norm

You won't know that until you find a better solution.

I can not find a better solution, that is why I am here for, to consult and draw on your experience.
I will attach the following function code that increments a binary number represented in a 1d array to the next larger number with the same number of bits valued 1.
If you can direct me on how to use this in order to find all different permutations of a 2d matrix NxN with K=(NxN)/4=bits valued 1 I'd appreciate it. I know this can help, because it increments the binary represented in the array and keeps a fixed number of bits valued 1.
Thank you.


I use the above function in another function that will increment the binary number represented in a 2d matrix as well, keeping a fixed number of bits valued 1. Even so it is successful, I still don't get all different permutations of a matrix NxN with (NxN)/4 bits valued 1.

I will attach here the following function, proven to work:
The function will get an array representing a binary number. It will increment this number to the next larger binary number with the exact same number of bits valued 1. It will return true if an increment was possible and keep the changes in the array, otherwise it will return false. It will increment in the following manner, starting from: 0 0 0 0 0 0 1 1 1

1d array: 0 0 0 0 0 1 0 1 1
1d array: 0 0 0 0 0 1 1 0 1
1d array: 0 0 0 0 0 1 1 1 0
1d array: 0 0 0 0 1 0 0 1 1
1d array: 0 0 0 0 1 0 1 0 1
1d array: 0 0 0 0 1 0 1 1 0
1d array: 0 0 0 0 1 1 0 0 1
1d array: 0 0 0 0 1 1 0 1 0
and so on until:
1d array: 1 1 1 0 0 0 0 0 0 (max)
This will allow me to get all permutations of a binary number with K bits valued 1 in an represented in an array. I need this to work for NxN matrix as well(more details after the code):


How can I use this function on a NxN matrix instead of an array? If a 2d matrix is an array of arrays, I can send every slot at a time. However, for the following matrix it will return false and make no changes while it should return true and make a change:
{{0,0,0},{0,0,0},{1,1,1}}
This will happen since each slot that is sent to the function will return false.
{1,1,1} - can not be incremented
{0,0,0} - has no bits valued 1 to increment it.
{0,0,0} - has no bits valued 1 to increment it.

However, the equivalent array: 0 0 0 0 0 0 1 1 1
will be incremented as shown in the beginning of the post.

How can I change this function to work for any given NxN binary matrix as well? that is, increment the binary number represented and keep the same number of bits valued 1?
Thank you.

P.S.
"public static boolean incrementKeepBits(int[] vec, int j, int counter)" must remain recursive.

Yes, you are right, it would fold that way. However, the function I am trying to get will receive a 2d matrix. I need to apply the changes for it. since i do have a properly working function for a 1d array, Perhaps I can transform the 2d matrix to a 1d array, make the change, and transform it back to a 2d matrix after the change is done. does it makes sense, how will i do that?

for a matrix nxn ill create a new array n^2 long. how though would i index m[i][j] in a lop into its respective slot array[k]?

ill use a counter inside the loops to track the array index.

for array back to matrix i think this would work

array[i]----goes to---->matrix[i/n][i%2]

n is always even and array size is n^2.

does that make sense?

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 3
at Draft.toArray(Draft.java:215)
at Draft.main(Draft.java:247)

is given. also, can i use math.sqrt(x) on int[] array.length?
please help me with this code.