Printable View
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.
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?
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.
Not sure how that works. What are the rows and the columns?Quote:
given a 2d matrix representing a binary number
How would 01101 be stored in a 2D array?
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.
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?
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).
Do that and discard those with the wrong number of 1sQuote:
I have an algorithm that could generate all possible binaries
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.
There is always more than one way. Solve it now, improve it later.
:) 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.
Get a working part for now and come back to it later.
You won't know that until you find a better solution.Quote:
inefficient as it may be
I can not find a better solution, that is why I am here for, to consult and draw on your experience.Quote:
Originally Posted by Norm
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.
Please edit your post and wrap your code with
[code=java]
<YOUR CODE HERE>
[/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.
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.
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.Quote:
use this function on a NxN matrix instead of an array?
For example:
0 0 0 0 0 1 0 1 1
would fold to:
0 0 0
0 0 1
0 1 1
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?
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.Quote:
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]?
The 1Dim array would need its own index, separate from the indexes for the 2Dim array.
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?
I'd use normal indexes to go through the 2Dim array and Have a separate index for the 1 Dim array
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
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.
Which index was out of bounds?
Add a println that prints out the values of the indexes so you can see.