Welcome to the Java Programming Forums

The professional, friendly Java community. 21,500 members and growing!

The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.

>> REGISTER NOW TO START POSTING

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

1. ## 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.  Reply With Quote

3. ## Re: Support Needed - Populating a 2d matrix with different binary number representations.

What code do you have so far?
I'm not sure I understand k: k=number places with value "1"
What is a "place"? One of the slots in the array?
Do the slots in the array hold a single bit with a value 0 or 1?  Reply With Quote

4. ## Re: Support Needed - Populating a 2d matrix with different binary number representations.

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.  Reply With Quote

5. ## Re: Support Needed - Populating a 2d matrix with different binary number representations.

given a 2d matrix representing a binary number
Not sure how that works. What are the rows and the columns?
How would 01101 be stored in a 2D array?  Reply With Quote

6. ## Re: Support Needed - Populating a 2d matrix with different binary number representations.

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.  Reply With Quote

7. ## Re: Support Needed - Populating a 2d matrix with different binary number representations.

Why a 2D array? The rows of the 2D array concatenated together make a single row to hold the number. first row + second row + third row = the number as 1D

What problems are you having? Do you have the algorithm for generating the binary numbers?  Reply With Quote

8. ## Re: Support Needed - Populating a 2d matrix with different binary number representations.

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).  Reply With Quote

9. ## Re: Support Needed - Populating a 2d matrix with different binary number representations.

I have an algorithm that could generate all possible binaries
Do that and discard those with the wrong number of 1s  Reply With Quote

10. ## The Following User Says Thank You to Norm For This Useful Post:

The Witchking (December 3rd, 2012)

11. ## Re: Support Needed - Populating a 2d matrix with different binary number representations.

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.  Reply With Quote

12. ## Re: Support Needed - Populating a 2d matrix with different binary number representations.

There is always more than one way. Solve it now, improve it later.  Reply With Quote

13. ## Re: Support Needed - Populating a 2d matrix with different binary number representations. 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.  Reply With Quote

14. ## Re: Support Needed - Populating a 2d matrix with different binary number representations.

Get a working part for now and come back to it later.

inefficient as it may be
You won't know that until you find a better solution.  Reply With Quote

15. ## Re: Support Needed - Populating a 2d matrix with different binary number representations. 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.  Reply With Quote

16. ## Re: Support Needed - Populating a 2d matrix with different binary number representations.

[code=java]
[/code]
to get highlighting and preserve formatting.

Also can you post a small. complete program that compiles and executes?

I've never seen a use for the algorithm you are looking for and don't know of one. Try googling to see if someone has posted the algorithm you are looking for.  Reply With Quote

17. ## Re: Support Needed - Populating a 2d matrix with different binary number representations.

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.  Reply With Quote

18. ## Re: Support Needed - Populating a 2d matrix with different binary number representations.

use this function on a NxN matrix instead of an array?
Can a 1Dim array be used to create a 2Dim array? Your earlier post showed a 2Dim array that looked like each row was a section from a 1Dim array.
For example:
0 0 0 0 0 1 0 1 1
would fold to:
0 0 0
0 0 1
0 1 1  Reply With Quote

19. ## Re: Support Needed - Populating a 2d matrix with different binary number representations.

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?  Reply With Quote

20. ## Re: Support Needed - Populating a 2d matrix with different binary number representations.

how will i do that?
With loops and indexing. If you can write the code in post#15, it shouldn't be hard to write code to convert an array's dim from 2 to 1 and back.  Reply With Quote

21. ## Re: Support Needed - Populating a 2d matrix with different binary number representations.

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]?  Reply With Quote

22. ## Re: Support Needed - Populating a 2d matrix with different binary number representations.

The 1Dim array would need its own index, separate from the indexes for the 2Dim array.  Reply With Quote

23. ## Re: Support Needed - Populating a 2d matrix with different binary number representations.

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?  Reply With Quote

24. ## Re: Support Needed - Populating a 2d matrix with different binary number representations.

I'd use normal indexes to go through the 2Dim array and Have a separate index for the 1 Dim array  Reply With Quote

25. ## Re: Support Needed - Populating a 2d matrix with different binary number representations.

What happens when the code is executed?
Use the Arrays class's toString() and deepToString() methods to format the arrays for printing before and after those methods execute to see what they are doing  Reply With Quote

26. ## Re: Support Needed - Populating a 2d matrix with different binary number representations.

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?  Reply With Quote
27. ## Re: Support Needed - Populating a 2d matrix with different binary number representations.  Reply With Quote