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 !!

If the target is to determine the number of combinations, then just apply the power: a^a. If you want the combinations itself, you will need recursion. — Martijn Courteaux
– Martijn Courteaux, Commented Apr 6, 2014 at 10:34
@weston I tought you wanted to create an iterative implementation... :) — TheConstructor
– TheConstructor, Commented Apr 6, 2014 at 11:13
@TheConstructor My lunch was ready, so I gave up, but I have now! — weston
– weston, Commented Apr 6, 2014 at 11:14

TheConstructor · Accepted Answer · 2014-04-06 10:54:47Z

3

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");
    }
}

answered Apr 6, 2014 at 10:54

TheConstructor

4,4951 gold badge34 silver badges55 bronze badges

Sign up to request clarification or add additional context in comments.

7 Comments

Aman Agnihotri Over a year ago

Don't you think that the number of combinations for a square table will always be table.length "to the power" table.length? Your program, though correct, can be further improved if you just print the combinations in the recursive calls, and when all is done, calculate the number of combinations using BigInteger's pow() method.

TheConstructor Over a year ago

@AmanAgnihotri yes it is and even OP stated in the introduction it is n^n. I am just mimicing the behavior of OP's solution to 5x5 table. Of course leaving out the count inside the recursion would also improve performance.

Aman Agnihotri Over a year ago

So I was thinking if you would do that. :) Still, +1.

TheConstructor Over a year ago

@AmanAgnihotri I am fine with this as it is. This way it will also work for arrays where each row has a different number of elements like new char[][] { new char[] {'A', 'B', 'C', 'D'}, new char[] {'E', 'F', 'G'}, new char[] {'H', 'I'}, new char[] {'J'} }. Of course if one row has no elements BigInteger.ZERO is returned and if it is new char[0][0] BigInteger.ONE is returned with [] as combination. I think that is the closest to mathematic combinatorics you can get in so few lines ;-)

weston Over a year ago

I can see why you think you should go for BigInteger. But have you considered how long a simple for loop over all the longs would take? i.e. for(long l=0;l<Long.MAX_VALUE;l++) What I am saying is that this code can take years to run if you even restricted it to longs. So if the problem requires BigInteger, they definitely need a different solution.

|

Community · Accepted Answer · 2017-05-23 12:05:22Z

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!!!

Audrius Meškauskas · Accepted Answer · 2014-04-06 10:44:37Z

0

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.

answered Apr 6, 2014 at 10:44

Audrius Meškauskas

21.9k12 gold badges85 silver badges100 bronze badges

3 Comments

TheConstructor Over a year ago

You still need table.length loops

Audrius Meškauskas Over a year ago

What to do mean by that?

TheConstructor Over a year ago

It's a square table and you choose one entry from each row

Teemu Ikonen · Accepted Answer · 2014-04-06 11:31:52Z

0

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);

answered Apr 6, 2014 at 11:31

Teemu Ikonen

12k4 gold badges25 silver badges35 bronze badges

Comments

Lajos Arpad · Accepted Answer · 2014-04-06 11:53:27Z

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);
    }
}

Scorpion_God · Accepted Answer · 2014-04-06 12:12:37Z

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))

Collectives™ on Stack Overflow

Number of elements combinations from 2D array are possible?

6 Answers 6

7 Comments

Comments

3 Comments

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

6 Answers 6

7 Comments

Comments

3 Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related