Questions tagged [matrix]
15 questions
19
votes
2 answers
How did Strassen come up with his matrix multiplication method?
The famous Strassen's matrix multiplication algorithm is a real treat for us, as it reduces the time complexity from the traditional O(n3) to O(n2.8).
But of all the resources I have gone through, even Cormen and Steven Skienna's book, they clearly…
user1369975
- 1,259
- 4
- 15
- 24
9
votes
5 answers
Which algorithm is performant for matrix multiplication of 4x4 matrices of affine transformations
I am wondering what is a good, performant algorithm for matrix multiplication of 4x4 matrices. I am implementing some affine transformations and I am aware that there are several algorithms for efficient matrix multiplication, like Strassen. But are…
wirrbel
- 3,018
- 2
- 21
- 33
7
votes
1 answer
Smallest Rubik's cube state representation
I'm trying to determine what is the fewest number of bits I need to represent the state of a Rubik's cube. (EDIT: I am assuming the cube is a valid Rubik's cube that has not been altered and only valid rotations have been performed. I am also…
J Price
- 89
- 5
4
votes
3 answers
What is the most effective algorithm to evenly distribute n points on a 2 dimensional array so they are as separated as possible?
I am trying to code a game which currently uses a matrix ( that I am calling a map). On this map are islands which can be generated n times. The purpose of the algorithm is to distribute the islands across the map in a way that makes use of the…
Ewan Ross
- 49
- 2
4
votes
5 answers
How to measure the solution level of an unsolved Rubik's Cube?
I am trying to figure out how to measure the relative success level of a given (but unsolved!) Rubik's Cube state. My first idea was to calculate the number of overlapping "cells" in the destination (solved) state and the given (unsolved) state, and…
Hendrik
- 149
- 1
3
votes
3 answers
Say we have a group of N person, and each person might want to sell or buy one of the M items, how to find a closed path among them for an exchange?
Say we have N persons and M items (when a person has a certain item, she usually only has one piece). For example,
person 1 has item A, C, D, and wants item F
person 2 has item B, C, and wants E
person 3 has item E, and wants G
...
You get the…
Jay
- 141
- 4
2
votes
3 answers
What Behavior would most users expect from a "Row Iterator" and a "Column Iterator"?
Let's say I have a Matrix class I've already implemented.
Matrix mat(30, 30);
for(size_t row = 0; row < mat.rows(); row++) {//Assume Row-Major ordering for performance reasons
for(size_t column = 0; column < mat.columns(); column++) {
…
Xirema
- 513
- 1
- 5
- 9
1
vote
3 answers
Memory on multiple cores versus 1 core
I am running a program that, among other things, does some matrix multiplications, singular value decompositions and accessing matrix subsets on a very large data set (these are the lines of code that take the most time).
I am running computations…
Andy
- 19
- 1
1
vote
1 answer
What is the most efficient way to represent resizable adjacecny matrix
I'm building a simple app that represents some matrix, where nodes are added quite often. Currently I have following code for adding a new node:
let mut new_edges = Array2::default((position + 1, position + 1));
for i in 0..position {
for j in…
Alex Zhukovskiy
- 111
- 5
1
vote
1 answer
Implementation of Matrix: std::vector vs std::unique_ptr?
As part of a hobby project, I needed a rectangular Matrix object to maintain state of a grid. At first, the implementation seemed trivial and unworthy of further discussion: (I haven't included all the code, only the relevant code)
template
Xirema
- 513
- 1
- 5
- 9
1
vote
2 answers
Place X items in N matrices without repeat column and row
I have N matrices (n × m) and items to place in each one (n · m). The same items are repeated randomly for each matrix. When one item is placed in (i, j), for the following matrices the item cannot be placed in the same row or column.
For…
user1532587
- 119
- 2
0
votes
0 answers
Quick way to check if there is a path in digraph
I have a finite directed graph (of several weakly connected components).
Having two elements I need to check if there is a path from the first one to the second one.
The easiest solution is to create the incidence matrix and then using it calculate…
porton
- 752
- 1
- 7
- 20
0
votes
1 answer
Algorithm to find the highest Tetromino in a Tetris board?
Lets say that our Tetris board is represented as a 2D array of zeros and ones, where a 0 means empty and 1 means occupied, and you where asked to find the highest row in which a tetromino exists.
Assuming that we didn't keep track of the height…
Raed Tabani
- 537
- 1
- 4
- 7
-1
votes
1 answer
Aligning text columns of different size and content
In a past posting, I asked about commands in Bash to align text columns against one another by row. It has become clear to me that the desired task (i.e., aligning text columns of different size and content by row) is much more complex than…
Michael Gruenstaeudl
- 117
- 8
-1
votes
1 answer
Rotate a matrix in place, moving elements? (How to write a part of flow/logic after understanding the problem?)
Following is a java solution of the classic question of rotating a nxn matrix in place clockwise by 90 degrees.
public void rotate(int[][] matrix, int n) {
for (int layer = 0; layer < n / 2; ++layer) {
int first = layer;
int last = n - 1 -…
Stacky
- 113
- 3