Creating every combination of a 2D array

[Jeff Sak]

If i was given a 2D array of {[1,2,3][4,5,6][7,8,9]} I want to be able to return [1,4,7][1,4,8][1,4,9][1,5,7] and so on. The length of the array will be the same as the number of arrays inside of the 2D array. So it will always be a 2X2 or 3X3 etc. I have so far been able to read in a file to create this 2D array but have only been able to figure out how to make a combination from a regular array and can't figure out how to make a loop that will create a combination from a 2D array. Any ideas on how I should structure my code to do this? I'm perfectly happy with psuedocode or just logic, I just can't seem to figure out how to make it so I can get every combination.

[Carey Brown]

Are the input dimensions always 3x3?

[Jeff Sak]

No sometimes they are 2X2 or 4X4. The thing is the column and rows will always be the same length so I was able to use that to read in the 2D array file into my program. I'm just not sure how to make it so I am getting every combination of it. I made a variable for arr[0].length so I know how big to make each array with the different combinations. I'm just never able to get the full list of combinations.

[Jeff Sak]

This is the code I have used to get every combination from a regular array, but I don't know how to transfer it to make it work for a 2D array or if it would translate over at all.

public static void printList(int arr[], int num, int combo){

        int temp[] = new int[combo];    //creating a temp array to store all combinations one at a time
        finalCombination(arr, temp, 0, num-1, 0, combo);  //calling function that will actually generate combos

    }

    public static void finalCombination(int arr[], int temp[], int start, int end, int index, int combo){

        if(index == combo){
            for(int i = 0; i<combo; i++){
                System.out.print(temp[i] + " ");     //for loop being called by recursive statement to place number in combo
            }
            System.out.println("");
            return;
        }

        for(int j = start; j <= end && end - j + 1 >= combo - index; j++){
            temp[index] = arr[j];
            finalCombination(arr, temp, j+1, end, index+1, combo);   //recursive statement
        }
    }

[Carey Brown]

Well, a brute force way to do a 3x3 array would be to have 3 nested loops.

for( int a = 0 ; a < N ; a++ ) {
    for( int b = 0 ; b < N ; b++ ) {
        for( int c = 0 ; c < N ; c++ ) {
            // build the output here
        }
    }
}

For a 2x2 array you'd need once less level and a 4x4 array you'd need one more level. Someone could probably come up with a nice recursive approach but I'm too tired right now. This give you at least something to think about.

[Piet Souris]

Have a method that extracts the i th element from all the arrays in the 2D array. and turns them into an int[] array.
A Stream example would be

private static int[] getEveryElementWithIndex(int[][] array, int index) {
    return Arrays.stream(array).mapToInt(ar -> ar[index]).toArray();
}

but a simple for-loop is of course also fine.

It should then be straight forward to get the result that you want. For this to work, all the arrays in the 2D array should be of the same length, but the number of arrays is unimportant. So, the input array might be 6 x 3, 11 x 2, et cetera.

[Carey Brown]

This works, whereas Piet's solution only seems to be a partial solution or a solution that doesn't answer the original post's requirements. Though I trust Piet could java-8-ify this or recurse-ify this.

	// A non-recursive solution
	// assumes an NxN square 2D array
	private static List<List<Integer>> permutations( int[][] array )
	{
		List<List<Integer>>	listList = new ArrayList<>();
		List<Integer>		list;
		int					n = array.length;
		int[]				idx = new int[n];
		
		for( boolean done=false ; ! done ; )
		{
			listList.add( list = new ArrayList<Integer>() );
			
			for( int j=0 ; j < n ; j++ )
				list.add( array[j][idx[j]] );
			
			for( int m=n-1 ; m >= 0 ; m-- )
			{
				if( idx[m] < n-1 )
				{
					idx[m]++;
					break;
				}
				idx[m] = 0;
				if( m == 0 )
					done = true;
			}
		}
		return listList;
	}

[salvin francis]

You mention combination, but I feel you actually mean permutation.
if [1,4,7] and [7,4,1] are both present, it is permutation.

Can you also confirm if you want repetition ?
eg [1,1,1] and [2,2,2]

[Piet Souris]

Carey Brown wrote:This works, whereas Piet's solution only seems to be a partial solution or a solution that doesn't answer the original post's requirements. (...)

Ahh, indeed, completely misread the problem...  sorry for that!

I do have a somewhat aging solution that uses streams. We had a topic some time ago  about getting all sublists of a list, and I can't remember who it was, but that someone produced a solution with Suppliers. If I can find that topic, I will have a look if I can incorporate some of that solution. My Stream version (with an added method to convert an int[][] to a List<List>>) with the disadvantage that it produces quite some Lists on the way.  The 1D arrays may be of any length:

public class CartesianProduct {
    
    public static void main(String... args) {
        int[][] input = { {1, 2}, {11, 22, 33}, {111, 222, 333, 444} };
        var lL = fromInt2DToListOfLists(input);
        var result = cartesianProductWithStreams(lL);
        result.forEach(System.out::println);
    }

    private static <T> Stream<List<T>> mapper(T t, List<List<T>> lists) {
        return lists.stream()
            .map(list -> {List<T> temp = new ArrayList<>(list); temp.add(t); return temp;})
        ;
    }
    
    private static <T> List<List<T>> flatMapper(List<List<T>> lists, List<T> list) {
        return list.stream().flatMap(t -> mapper(t, lists)).collect(toList());
    }
    
    public static <T> List<List<T>> cartesianProductWithStreams(List<List<T>> lists) {
        List<List<T>> start = new ArrayList<>();
        start.add(new ArrayList<>());
        return lists.stream().reduce(start, (a, b) -> flatMapper(a, b), (a, b) -> a);
    }
    
    private static List<List<Integer>> fromInt2DToListOfLists(int[][] input) {
    return Arrays.stream(input)
        .map(ar -> Arrays.stream(ar).boxed().collect(toList()))
        .collect(toList());
    }
}

As an alternative:
if we have T arrays, with length t0, t1, t2, ... then we have as outcome N = t0 * t1 * ... arrays (or Lists). So we can run a loop from 0 to N-1, with 0 meaning pick fro every array the 0th element, 1 meaning pick from every array the 0th element, but element 1 from the last array, et cetera. So in fact we express every number X in a number with the explained base, and so we can directly calculate the result involved. For the true enthousiast!

[Elad Kapuza]

This is actually working!!!
Hope it helps.

def generate_board(board, row, col, min_val, max_val):
   # all matrix is filled
   if row == len(board)-1 and col == len(board[0]):
       tmp = []
       print('-----------')
       for line in board:
           tmp.append(line)
           print(line)
       return

   # next row
   if col == len(board[0]):
       generate_board(board, row+1, 0, min_val, max_val)

   # return
   if row == len(board):
       return

   # loop over all possible values
   for value in range(min_val, max_val+1):
       if col < len(board[0]):
           board[row][col] = value
           # next element in row
           generate_board(board, row, col+1, min_val, max_val)
           board[row][col] = min_val

   return

[Campbell Ritchie]

Welcome to the Ranch

Which language is that? Is it JS?