I recently got this question (paraphrased below) in a practice interview test and it still stumps me:

Given a 2d array A, generate a list of row-wise 1d array permutations from it.

A = [
     [1],
     [5, 2],
     [6]
     ]

Answer: [[1, 5, 2, 6], [1, 6, 5, 2], [5, 2, 1, 6], [5, 2, 6, 1], [6, 1, 5, 2], [6, 5, 2, 1]]

Explanation of answer: We are permuting on the rows, so it's like generating permutations for [a,b,c] where each of these elements is a 1d array of potentially varying length.

I'm sure the solution involves backtracking, but anytime I try to implement it I end up with a 5 parameters. I was hoping one of you folks could kindly provide an elegant solution, pseudocode, or explanation.

CodePudding user response：

You're really just permuting the row order, and then flattening the matrix for each permutation. Python example:

from itertools import chain, permutations

def flatten(matrix):
    return list(chain(*matrix))

def permute(matrix):
    return [flatten(perm) for perm in permutations(matrix)]

With your example:

>>> M = [[1], [5, 2], [6]]
>>> permute(M)
[[1, 5, 2, 6], [1, 6, 5, 2], [5, 2, 1, 6], [5, 2, 6, 1], [6, 1, 5, 2], [6, 5, 2, 1]]

In another language, you may have to implement your own helper functions to iterate through permutations (possibly using recursion), and list flattening.

CodePudding user response：

In Java you can do it like the following(first get a permutation of all the indexes and then use that to generate the ans):

public class RowWisePermutation {
    
    public static void main(String[] args) {
        int[][] A = {
                         {1},
                         {5, 2},
                         {6}
        };
        generateRowWisePermutation(A);
    }
    
    public static List<List<Integer>> generateRowWisePermutation(int[][] matrix) {
        List<Integer> temp = new ArrayList<>();
        List<List<Integer>> ans = new ArrayList<>();
        
        List<List<Integer>> indexPermutation = new ArrayList<>();
        int[] indexArr = new int[matrix.length];
        for(int i = 0; i < matrix.length; i  ) {
            indexArr[i] = i;
        }
        backtrack(indexArr, temp, indexPermutation);
        
        System.out.println(indexPermutation);
        for(int i = 0; i < indexPermutation.size(); i  ) {
            List<Integer> row = new ArrayList<>();
            List<Integer> indices = indexPermutation.get(i);
            for(Integer index : indices) {
               for(int j = 0; j < matrix[index].length; j  ) {
                   row.add(matrix[index][j]);
               }
            }
            ans.add(row);
        }
        System.out.println(ans);
        return ans;
            
    }
    
    private static void backtrack(int[] arr, List<Integer> temp, 
            List<List<Integer>> indexPermutation) {
        
        if(temp.size() == arr.length) {
            indexPermutation.add(new ArrayList<>(temp));
            return;
        }
        
        for(int i = 0; i < arr.length; i  ) {
            if(temp.contains(i)) { continue; }
            temp.add(arr[i]);
            backtrack(arr, temp, indexPermutation);
            temp.remove(temp.size() - 1);
        }
    }
}