Matrix multiplication by rearranging

Question

I have a list of matrix dimensions like:

(1, 2), (3, 2), (2, 3), (3, 1)

I want to rearrange the matrix dimensions so that all of them can be multiplied. For the above one, we can rearrange them:

(3, 1), (1, 2), (2, 3), (3, 2)

How can I find this for a large number of dimensions up to 2000?

I have tried next_permutation in C++ but it's not efficient when the number of dimensions is big.

Answer 1

From the idea provided in the previous answer, you could do:

using MatrixDimensions = std::vector<std::pair<int, int>>;
auto add_one(const MatrixDimensions &vec){
    //find all the unique values ie 1,2,3
    std::vector<int> vals;
    for (auto const &v: vec){
        vals.push_back(v.first);
        vals.push_back(v.second);
    }
    std::sort(vals.begin(), vals.end());
    auto it = std::unique(vals.begin(), vals.end());
    vals.resize(distance(vals.begin(), it));
    
    // count the number of each unique value in the rows and columns
    std::unordered_map<int, int> row;
    std::unordered_map<int, int> column;
    for(auto const &i : vec){
        row[i.first] += 1;
        column[i.second] += 1;
    };
    
    // find the difference between row column counts
    std::unordered_map<int, int> diff;
    
    for (auto val: vals){
        if (row.find(val) != row.end()){
            if(column.find(val) != column.end()) 
                diff[val] = row[val] - column[val];
            else diff[val] = row[val];
        }
        else diff[val] = -column[val];
    }
    // add the missing dimension:
    std::pair<int,int> added_one = vec[0];
    for(auto const &i: diff) 
        if (i.second == -1)added_one.first = i.first;
        else if (i.second == 1) added_one.second = i.first;
    return added_one;
}

MatrixDimensions arangeForMutiplication(const MatrixDimensions& dimensions){
    if (dimensions.size() < 2) return dimensions;
    MatrixDimensions result{add_one(dimensions)};
    MatrixDimensions vec{dimensions};
    //create a cycle beginning from the added position then delete the first
    while(!vec.empty()) {
        auto it = std::find_if(vec.begin(), vec.end(),
            [=](std::pair<int, int> a) {
                return a.first == result.back().second;
            });
        result.push_back(*it);
        vec.erase(it);
    }
    result.erase(result.begin());
    return result;
}

Check out the code here which gives out the following:

(3,2) (2,3) (3,1) (1,2)

Note that we could test this and it passes all given cases:

Answer 2

Let's assume for simplicity that for all numbers N, the number of matrices with N rows is the same as the number of matrices with N columns. If this is not the case, then there should be exactly one matrix missing, otherwise there's no solution. For the given example, a (2,3) matrix is missing. Just add that one missing matrix. We will remove it at the final stage of the solution.

Now that we have our condition satisfied, the matrices can be arranged in a cycle. For our example, it's (3, 1), (1, 2), (2, 3), (3, 2), (2, 3) and the last 3 connects with the first one. Note: yes, as alluded in the comments, this is a Hamiltonian cycle in a matrix connectivity graph, but this class of graphs is special, and the problem is in fact easier than the general Hamiltonian cycle problem. We can cut the cycle anywhere and that would be a valid solution (of the modified problem).

Now let's run a greedy algorithm. Take any matrix, find any matrix that can be multiplied with it, then find another matrix that can be added to the chain, etc. Repeat until there is no matrix that can be added.

• Claim: the resulting chain can be closed into a cycle.
• Proof sketch: notice the starting number of the chain, count how many times it is included in the chain.

So we have built a cycle. If it includes all the matrices from the set, we are done. If not, we take the set of remaining matrices that did not end up in the cycle, and solve the problem for it (it is smaller than the original problem). Note that the number of matrices with N rows is still the same as the number of matrices with N columns in the remaining set (because this is true about the original set, and is true about the cycle just built). Now we have several cycles.

Find two cycles that have a dimension in common (that is, there is a fragment ... N), (N... in both cycles). Cut both at that place, and join so that they make a bigger cycle. Repeat until a single cycle remains. If at some point there are no two cycles that can be joined, there is no solution (each cycle represents a strongly connected component in the graph).

So now we have a cycle that possibly contains one extra matrix that we have added at the beginning. We just throw that matrix away. If we have not added anything, we can cut the cycle at an arbitrary place.