Swapping the columns of a matrix with every other column

I'd like to produce lists that represent the different permutations of swapping the columns of a matrix.

For example if I had and I wanted to produce two lists:

1) [ab, cd]

2) [ba,dc]

The matrix I am actually dealing with is 200x10

I have tried using

for i = 1 : 4
        d = a_x(:, i)
        a_x(:, i) = a_x(:, i + 1)
        a_x(:,i + 1) = d
end

but it is not very efficient.

[Matt J]

It looks like it should be very efficient, as long as your goal is only to swap neighboring columns. If your goal is to find all factorial(10) column permutations, that goal needs to be reconsidered. For a 200x10 matrix, you would need 27 GB to store the result (in single floats).

[Robert Elston]

The plan is to swap all columns with each other; not just neighboring ones.

[Robert Elston]

Perhaps if the first 6 were swapped with each other and the last four with each other?

[James Tursa]

What are you doing with these matrices downstream in your code? Maybe you can accomplish your desired result, or a statistical representation of your final result, without physically generating all of the matrices.

Answer 1

[David Goodmanson]

Hi Robert,

Going with permutaions of the first six columns in conjuction with permutations of the last four columns certainly reduces the size of the problem by a huge factor, down to 'only' 17,280 matrices (or lists, if you prefer that name). But still, if you were to save those matrices you would be saving a lot of redundant information. The only thing that matters is the order of the columns, not really the contents of each one because you have the original matrix available. So with 200 rows you are saving 200 times as much information as you need.

In addition, how would you name the matrices so that you can access them? Dynamically named objects, (i.e. a separate name for each matrix) are definitely not a good idea because the code is susceptible to error and difficult to modify.

For matrix A with 10 columns, and a given permutation, say p = [3 6 2 1 5 4 10 7 9 8], what comes to mind for a name is A36215410798. But all you are doing is freezing in stone a process that is easily done on the spot. For a given permutation you can just do

B = A(:,p)

when needed.

Going back to the case of N columns and N! permutations, it makes much more sense to map each permutation to an index that runs from 1 to N! Then an index can produce a permutation which can produce a matrix as above. Here is some code that produces permutations from indices in bijective (one-to-one) fashion.

function j = ind2perm(N,n);

% index n mapped onto permutation j of N objects, with 1 <= n <= N!
% inverse function is perm2ind
% David Goodmanson
%
% j = ind2perm(N,n);

n = n-1;                       % zero based calculation
j = zeros(1,N);
int = 1:N;
for k = N:-1:1
  a = rem(n,k)+1;              % euclidean remainder +1
  n = floor(n/k);
  j(N-k+1) = int(a);
  int(a) = [];
end

function n = perm2ind(j);

% permutation j of N objects mapped onto index n, with 1 <= n <= N!
% inverse function is ind2perm
% David Goodmanson
%
% n = perm2ind(j);

N = length(j);
c = cumprod(N+1:-1:2)/(N+1);
int = 1:N;
n = 0;
for k = 1:N-1;
  f = find(int==j(k));           % euclidean remainder +1
  int(f) = [];
  n = n + (f-1)*c(k);
end
n = n+1;                         % go to one-based index

[Robert Elston]

Thanks for this. I've ended up using python because it was able to do the permutations without storing the result as a matrix and clogging up memory, or running out of indices! Your answer is really helpful though. I neede to do all 10! and I am currently 400000 in... The good thing is that I learn from everything even if it is wrong.