Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
how do I count the permutations that were performed

Subject: how do I count the permutations that were performed

From: Gilles

Date: 25 Nov, 2008 02:50:17

Message: 1 of 6

How do I count the permutations that were performed during lu factorization? For instance, I get back the permutation matrix. Is there a way I could calculate how many permutations that permutation matrix represents?

Subject: how do I count the permutations that were performed

From: Bruno Luong

Date: 25 Nov, 2008 07:42:05

Message: 2 of 6

"Gilles " <louvre65662@mypacks.net> wrote in message <ggfp59$87b$1@fred.mathworks.com>...
> How do I count the permutations that were performed during lu factorization? For instance, I get back the permutation matrix. Is there a way I could calculate how many permutations that permutation matrix represents?

One ? Given by the permutation matrix P.

Your question is unclear.

Any permutation P can be decomposed as smaller independent inner circular-shift, each circular shift (length c) is in turned composed by c-1 (?) elementary swapping.

If is not very difficult to make such decomposition. But just wonder why you need it?

Bruno

Subject: how do I count the permutations that were performed

From: Gilles

Date: 25 Nov, 2008 18:46:02

Message: 3 of 6

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message
> Your question is unclear.
>


Thanks for your response. See what I want to find out is how many row swaps had been performed while pivoting. I've been thinking about it some more, and I think it should be possible to work just with the permutation vector.

Gilles

Subject: how do I count the permutations that were performed

From: Bruno Luong

Date: 25 Nov, 2008 19:16:36

Message: 4 of 6

"Gilles " <louvre65662@mypacks.net> wrote in message <gghh5a$f7f$1@fred.mathworks.com>...
> "Bruno Luong" <b.luong@fogale.findmycountry> wrote in message
> > Your question is unclear.
> >
>
>
> Thanks for your response. See what I want to find out is how many row swaps had been performed while pivoting. I've been thinking about it some more, and I think it should be possible to work just with the permutation vector.

Yes permutation vector is all you need.

If you want to decompose, then follow this procedure:

- to figure out cycle inside P, start with k=1, iterate k=P(k) until k equal 1 (round robin).
  Let's call this cycle C1 ( := { P^j(1): j=1, 2, ... } )
- Remove the cycle C1 from the set {1,2,..., n}
- Take k=the first element of set difference, and continue to localize a next cycle until nothing left.
- I let you figure out how to decompose each cycling permutation into many consecutive two-element-swaps.

Though I can hardly think what purpose you might need this decomposition.

Bruno

Subject: how do I count the permutations that were performed

From: Bruno Luong

Date: 25 Nov, 2008 21:22:01

Message: 5 of 6

OK Here is for fun the program that count the number of swaps in a random permutation:

%%%%%%%%%%%%%%%%%%
% swapfactor.m

function swapidx = swapfactor(P)
% Decompose P as list of of atomic swap permutation

mask=false(size(P));
swapidx = [];
% Loop until all element are marked
while ~all(mask)
    [C mask] = getonecycle(P, mask);
    if length(C)>1
        sC = [C(1:end-1) C(2:end)];
        swapidx = [swapidx; sC]; %#ok
    end
end

end % swapfactor

function [C mask]= getonecycle(P, mask)
% Get on cycle

k0=find(~mask,1,'first');
k=k0;
Pk=0;
C=[];
while Pk~=k0;
    mask(k)=true;
    Pk=P(k);
    C(end+1)=Pk; %#ok
    k=Pk;
end

% reshape in column
C=C(:);

end % getonecycle

%%%%%
% swap.m
function P = swap(P, i1, i2)
   [P(i2) P(i1)] = deal(P(i1),P(i2));
end % swap

% Test in command line

P=randperm(10)
% Decompose P as list of of atomic swap permutation
swapidx = swapfactor(P);

ns = size(swapidx,1);
fprintf('Numer of swaps = %d\n', ns);

% Test
n=length(P);
Q=1:n;
for j=1:ns
   Q=swap(Q,swapidx(j,1),swapidx(j,2));
end

Q

% Bruno

Subject: how do I count the permutations that were performed

From: Gilles

Date: 25 Nov, 2008 23:07:02

Message: 6 of 6

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <gghq9p$in1$1@fred.mathworks.com>...
> OK Here is for fun the program that count the number of swaps in a random permutation:
!
Excellent! Thanks,

Gilles

Tags for this Thread

No tags are associated with this thread.

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us