Number of elements combinations from 2D array are possible?

Question

I have 5x5 element table. Let's say each row in that table is a jar. Each element in row is a different color ball in a jar. We are taking one ball from first jar, one ball from second, one ball from third... and so on to 5th jar. We have 5 ball color combination... then we put ball's back to relevant jars. Question : how many combination variants is possible ? Answer n ^ n , where n is table size !

The problem is, I never know what how big table is, though is always symetric (n x n) elements. I want to write UNIVERSAL method which will return all possible color combinations.

For table 5x5 elements it would look like this :

private int combinations = 0;
private char table[][] = { {'A','B','C','D','E'},
                           {'F','G','H','I','J'}, 
                           {'K','L','M','N','O'},
                           {'P','Q','R','S','T'},
                           {'U','V','X','Y','Z'}};  

public Prog() {     

    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 5; j++) {
            for (int k= 0; k < 5; k++) {
                for (int l = 0; l < 5; l++) {
                    for (int m = 0; m < 5; m++) {

                        System.out.println(table[0][i] +" " + table[1][j]+ " " + table[2][k]+ " " + table[3][l]+ " " + table[4][m]);                            
                        combinations++;
                    }
                    System.out.println("--------------");
                }                   
            }
        }           
    }       
    System.out.println("Total combination is : " + combinations);   
}

... but above code is only for 5x5 table. If I got 4x4, or 3x3, I need to modify all the for loops to work properly... Would somebody please help me to write a method that would modify itself acording to table size and return proper combinations ?

Thanks !!

Answer 1

Recursive solution to this problem:

import java.math.BigInteger;
import java.util.Arrays;

/**
 * Created for http://stackoverflow.com/q/22892808/1266906
 */
public class Combinations {

    public static BigInteger printCombinationsRecursively(char[][] table) {
        return printCombinationsRecursively(table, new char[table.length], 0);
    }

    public static BigInteger printCombinationsRecursively(char[][] table, char[] selection, int currentRow) {
        if(currentRow >= table.length) {
            System.out.println(Arrays.toString(selection));
            return BigInteger.ONE;
        }
        BigInteger count = BigInteger.ZERO;
        for (char c : table[currentRow]) {
            selection[currentRow] = c;
            count = count.add(printCombinationsRecursively(table, selection, currentRow + 1));
        }
        return count;
    }

    public static void main(String[] args) {
        char[][] table = new char[][] {
                new char[] {'A', 'B', 'C', 'D'},
                new char[] {'E', 'F', 'G', 'H'},
                new char[] {'I', 'J', 'K', 'L'},
                new char[] {'M', 'N', 'O', 'P'}
        };
        final BigInteger combinations = printCombinationsRecursively(table);
        System.out.println(combinations + " combinations");
    }
}

Answer 2

Iterative version with identical output for the 5x5 array:

void Prog() {
    int baseN = table.length;
    int maxDigits = table[0].length;
    int max = (int) Math.pow(baseN, maxDigits);
    // each iteration of this loop is another unique permutation
    for (int i = 0; i < max; i++) {
        int[] digits = new int[maxDigits];
        int value = i;
        int place = digits.length - 1;
        while (value > 0) {
            int thisdigit = value % baseN;
            value /= baseN;
            digits[place--] = thisdigit;
        }

        int tableIdx = 0;
        for (int digitIdx = 0; digitIdx < digits.length; digitIdx++) {
            int digit = digits[digitIdx];
            System.out.print(table[tableIdx][digit] + " ");
            tableIdx++;
        }
        System.out.println();
        combinations++;
        if (i % maxDigits == maxDigits - 1)
            System.out.println("--------------");
    }
    System.out.println("Total combination is : " + combinations);
}

It is based on my answer https://stackoverflow.com/a/9315076/360211, I'm treating this as a 5 digit, base 5 number.

Note because I use int for max and you use it for combinations, the limit for this is a 9x9 array, because 10^10 > Integer.MAX_VALUE. long will give you up to 15x15, but that will take years to run!!!

Answer 3

Use the .length field of the array to determine the size of the table:

for (int i = 0; i < table.length; i++) {
    (..)

This field always contains the right size of the array.

Answer 4

I think the approaches are not very optimal, here is general way to get permutations from NxN table. This is in Javascript but gives idea of the method

var table = [ ['A','B','C','D','E'],
              ['F','G','H','I','J'],
              ['K','L','M','N','O'],
              ['P','Q','R','S','T'],
              ['U','V','X','Y','Z']];


function perm(l) {
    var n = Math.pow(l.length,l.length);
    for(var i=0; i < n; i++) {
        var s = '';
        var m = i;
        for(var k=0 ; k < l.length; k++) {
            var p = m % 5;
            s += l[k][p];
            m = ~~(m / 5);
        }
        console.log(s);
    }
}

perm(table);

Answer 5

Here is a readable and easy-to-solve solution: Let's treat it as an n-base number having n digits.

Let's suppose you have an array which stores the digits (possible colors). In this case you can generate the permutations (and not combinations) this way (code is untested):

public int[] nextPermutation(int[] input, int base) {
    if (input == null) {
        int[] returnValue = new int[base];
    }

    int modulo = 1;
    for (int digitIndex = 0; (modulo > 0) && (digitIndex < input.length); digitIndex++) {
        input[digitIndex] = (input[digitIndex] + 1) % base;
        modulo = ((input[digitIndex] > 0) ? (1) : (0));
    }

    return ((modulo == 0) ? (input) : (null));
}

public int[] getColorByPermutation(int[] permutation, int[] colors) {
    int[] result = new int[permutation.length];
    for (int permutationIndex = 0; permutationIndex < permutation.length; permutation++) {
        result = colors[permutation[permutationIndex]];
    }
}

public void generatePermutations(int base, int[] colors) {
    int permutation = nextPermutation(null, base);
    while (permutation != null) {
        int[] currentColors = getColorByPermutation(permutation, colors);
        //Do whatever you need with the colors
        permutation = nextPermutation(permutation, base);
    }
}

Answer 6

Unfortunately I only know Python, but I think the following two solutions will do what you want.

Recursive

class Permutations:
    def __init__(self, matrix):
        self.matrix = matrix
        self.n = len(matrix)
        self.permutations(self.n)
        print('There are {} permutations!'.format(self.n**self.n))

    def permutations(self, count, sequence=[]):
        if count == 0:
            chars = [self.matrix[i][sequence[i]] for i in range(self.n)]
            print(' '.join(chars))
            return None
        for x in range(self.n):
            self.permutations(count-1, sequence+[x])
        if count == 1:
            print('---------------')

Iterative

def decimal_to_base_n(decimal, base):
    digits = []
    while decimal:
        digit = decimal%base
        digits.append(digit)
        decimal //= base
    digits += [0]*(base-len(digits))
    return digits[::-1]

def permutations(matrix):
    n = len(matrix)
    for i in range(n**n):
        sequence = decimal_to_base_n(i, n)
        chars = [matrix[j][sequence[j]] for j in range(n)]
        print(' '.join(chars))
        if i%n == n-1:
            print('---------------')
    print('There are {} permutations!'.format(n**n))