Path: news.mathworks.com!not-for-mail
From: "Bruno Luong" <b.luong@fogale.findmycountry>
Newsgroups: comp.soft-sys.matlab
Subject: Re: how do I count the permutations that were performed
Date: Tue, 25 Nov 2008 21:22:01 +0000 (UTC)
Organization: FOGALE nanotech
Lines: 65
Message-ID: <gghq9p$in1$1@fred.mathworks.com>
References: <ggfp59$87b$1@fred.mathworks.com> <ggga8d$i6r$1@fred.mathworks.com> <gghh5a$f7f$1@fred.mathworks.com> <gghiuk$h66$1@fred.mathworks.com>
Reply-To: "Bruno Luong" <b.luong@fogale.findmycountry>
NNTP-Posting-Host: webapp-02-blr.mathworks.com
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: 8bit
X-Trace: fred.mathworks.com 1227648121 19169 172.30.248.37 (25 Nov 2008 21:22:01 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Tue, 25 Nov 2008 21:22:01 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 390839
Xref: news.mathworks.com comp.soft-sys.matlab:503193

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