Randomly permute rows/columns of a matrix with eigen

Question

I'm using Eigen and I've got a matrix:

MatrixXi x = MatrixXi::Random(5);

I'd like to randomly permute the rows and columns using a randomly drawn permutation (just one permutation for both the rows and columns), i.e. if I have a permutation that sends indices [0,1,2,3,4] -> [3,4,2,1,0] than I want to reorder the rows and the columns with the same permutation.

Part 1: I can't find an example of PermutationMatrix online, and I'm having trouble figuring out the syntax.

Part 2: how do I obtain a randomly permuted vector of indices to pass to it? Maybe std::random_shuffle?

update:

Here is a (probably inefficient) way to get a shuffled set of indices:

std::vector<int> perm;
for (int i=0; i<5; ++i) {
    perm.push_back(i);
}

std::random_shuffle(perm.begin(), perm.end());

So now the question is how I do reorder my matrix x so that it's rows/columns are ordered by perm?

update 2:

Getting closer, this works (source for ideas: cplusplus.com):

int myrandom (int i) { return std::rand()%i;}

PermutationMatrix<Dynamic,Dynamic> perm(5);

perm.setIdentity();
for (int i=dim-1; i>0; --i) {
    swap (perm.indices()[i],perm.indices()[myrandom(i+1)]);
}

cout << "original x" << x << endl << endl;
cout << "permuted x" << perm * x * perm << endl << endl;

Anyone know how to do this with random_shuffle? (see attempt that didn't work below.)

(Bonus: any thoughts on whether perm * x * perm will be efficient if perm is a 1e4 x 1e4 matrix?)

Jueta

Answer 1

Using std::random_shuffle is perfectly fine, then you have to use a PermutationMatrix:

PermutationMatrix<Dynamic,Dynamic> perm(size);
perm.setIdentity();
std::random_shuffle(perm.indices().data(), perm.indices().data()+perm.indices().size());
A_perm = A * perm; // permute columns
A_perm = perm * A; // permute rows

Eleneeleni

Thanks ggael. This is close, but perm.indices() doesn't have iterators AFAIK. I get error: ‘Eigen::PermutationMatrix<-1, -1>::IndicesType’ has no member named ‘begin’. I edited my question with half-baked, but as far as I can tell working code, but I would still love to figure out how to get this to use random_shuffle! – Jueta

Quite update for anyone who finds this on Google: if you want to apply the same permutation to both rows and columns you need to use: perm.transpose() * x * perm – Jueta

Doesn't this seem like an inefficient way to do this? I would image that permuting rows can be a lot faster than multiplying matrices, especially if they are large. – Cangue

This is exactly what PermutationMatrix::operator* is doing! It can even work in-place if you write: A = perm * A. – Eleneeleni

For some reason the "in-place" operator was a lot slower than the non-in place one.. :| – Mechanic

The inplace version is indeed more involved because you have to follow and track the cycles.. but it avoids a temporary. – Eleneeleni

Answer 2

As stated here: Stackoverflow:

If you can use C++11 I'd recommend implementing this without using srand() and random_shuffle(); instead you should use the <random> library with std::shuffle.

First, if possible rand should be avoided. Aside from the fact that it isn't usually a very good pRNG, it also has problems with thread safety due to shared state. The <random> library fixes both these problems by giving the programmer explicit control over pRNG state and by providing several options with guaranteed performance, size, and quality characteristics.

Secondly, random_shuffle isn't actually specified to use rand so it's theoretically legal for reseeding using srand not to have the effect you want. To get guaranteed results with random_shuffle you have to write your own generator. Moving to shuffle fixes that, as you can directly use standard engines.

#include <random>       //seed generation
#include <algorithm>    //shuffle()

int main() {

std::random_device r;
std::seed_seq rng_seed{r(), r(), r(), r(), r(), r(), r(), r()};

//create random engines with the rng seed
std::mt19937 eng1(rng_seed);

//create permutation Matrix with the size of the columns
Eigen::PermutationMatrix<Eigen::Dynamic, Eigen::Dynamic> permX(inputX.cols());
permX.setIdentity();
std::shuffle(permX.indices().data(), permX.indices().data()+permX.indices().size(), eng1);
inputX = inputX * permX;   //shuffle column wise

}

If you want to shuffle the rows use inputX.rows() instead for the initialization of the Permutation Matrix. And use inputX = permX * inputX instead.

Cavan

I like the attention to details in this answer more than the original accepted one – Proselytize