permutate binary matrix java

Question

im tring to get all the possibles combination of a binary matrix NxM with a variable thats says how many 1's it has, on Java.

For example:

matrix = 0 0 0 0
         0 0 0 0

run the method with like:

permute(matrix,3);

result list = 1 1 1 0 1 0 1 1 0 1 1 1 1 0 0 0 1 0 0 0 ... 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 ...

i try to do it by arrays of the matrix, but i think its a bad idea. there must be an easier way.

Instead of solving the problem as a matrix, try to model it as a single array that contains NxM values and permute it to get all the possible combinations. Then you can convert it back to matrix format — ruthless, Jul 09 '14 at 02:46
An NxM matrix can be mapped to an array that is NxM long. so simply apply the solution found here: http://stackoverflow.com/questions/1851134/generate-all-binary-strings-of-length-n-with-k-bits-set — vandale, Jul 09 '14 at 02:46
so do you want technical help or do you want a mathematical solution?. Just another question, do you want a permuatation, or combination? — harveyslash, Jul 09 '14 at 03:03

score 2 · Accepted Answer · answered Jul 09 '14 at 04:01

The answer given in the comments on your question is for a C-based language. This solution is made for Java. Call permute and give it the matrix as a 1 dimensional array, and it will return an ArrayList of all the permutations as MyMatrix objects, so you can include more data about the matrices if you want. If you wanted to be more memory efficient, you could use all the bytes of the char and use bit shifting, but this code doesn't. This is a recursive algorithm to solve your problem. I'm pretty sure this works, and I hope it helps!

public ArrayList<MyMatrix> permute(char[] array, int num)   //array is the 2D matrix as a single 1D array that is NxM big
{
    ArrayList<MyMatrix> permutations = new ArrayList<MyMatrix>();
    getPermutation(0, num, 0, array.clone(), permutations);  //clone so we don't break the original
    return permutations;
}

public void getPermutation(int depth, int maxDepth, int index, char[] array, ArrayList<MyMatrix> permutations)
{
    if ((index == array.length) || (depth == maxDepth))
    {
        //have to clone because we generate all permutations from the same array
        MyMatrix permutation = new MyMatrix(array.clone());
        permutations.add(permutation);
        return;
    }

    for (int i = index; i < (array.length - (maxDepth-depth)); i++)
    {
        getPermutation(depth+1, maxDepth, index+1, array, permutations);
        array[index] = 1;
        getPermutation(depth+1, maxDepth, index+1, array, permutations);
        array[index] = 0;   //make it as if nothing happened to the number
    }
}

public class MyMatrix
{
    char[] matrix;
    int numOnes;

    public MyMatrix(char[] array)
    {
        matrix = array;
        numOnes = 0;
        for (int i = 0; i < matrix.length; i++)
        {
            if (matrix[i] = 1)
            {
                numOnes++;
            }
        }
    }
}

permutate binary matrix java

1 Answers1