BioConsert Project – February 2011

Our heuristic to find a consensus for a set "ens" containing "card" rankings of [n], starting in ranking "tri"

BioConsert:=proc(tri,cost_matrix(ens),card,n)
  local compte,bool,i,k,temp,paquet,pos;
  bool:=0;
  temp:=tri;
  while bool <> 1 do
    compte:=0;
    paquet:=nops(temp);
    pos:=position(temp,n);
    for i from 1 to n do
      for k from 1 to paquet+1 do
       if k < paquet+1 then
         if CoutChangePaquet(MatCout,card,pos,i,k,n) < 0 then
            temp:=changePaquet(temp,pos,i,k);
            compte:=compte+1;
            k:=paquet+2;
            i:=n+1;
         elif CoutNewPaquet(MatCout,card,pos,i,k-1,n) < 0 then
            temp:=NewPaquet(temp,pos,i,k-1);
            compte:=compte+1;
            k:=paquet+2;
            i:=n+1;  
         fi;
       else
          if CoutNewPaquet(MatCout,card,pos,i,k-1,n) < 0 then
            temp:=NewPaquet(temp,pos,i,k-1);
            compte:=compte+1;
            k:=paquet+2;
            i:=n+1;  
          fi;
      fi;
     od;
    od;
  if compte = 0 then
    bool:=1;
  fi;
  od;
temp;
end:

Generate a matrix containing in position [i,j] the Kendall-tau distance of pair (i,j) with respect to the rankings of [n] of set "ens" 

cost_matrix:=proc(ens,n)
 local cout,i,j,k,m,pos;
 cout:=Array(1..n,1..n);
 for m from 1 to nops(ens) do
    pos:=position(ens[m],n);
    for i from 1 to n do
      for j from i+1 to n do
          if pos[i] < pos[j] then 
              cout[j,i]:=cout[j,i]+1;
          elif pos[i] > pos[j] then 
              cout[i,j]:=cout[i,j]+1;
          fi;
      od;
    od;
od;
cout;
end:

Generate an array of length n containing in position i, the position of i in the ranking i.e. the index of the bucket containing i 

position:=proc(liste,n)
local i,j,pos;
pos:=Array(1..n);
for i from 1 to nops(liste) do
   for j from 1 to nops(liste[i]) do
       pos[liste[i][j]]:=i;
   od:
od;
pos;
end:

Compute the cost of putting integer i in bucket k in ranking tri of [n]  (MatCout=cost_matrix(ens), pos=position(tri), card= cardinality of ens)

CoutChangePaquet:=proc(MatCout,card,pos,i,k,n)
  local res,temp,m,cout_avant,cout_apres,cout;
  cout_avant:=0;
  cout_apres:=0;
  for m from 1 to n do
    if m<>i then
       if pos[i] < k then
          if pos[m] > pos[i] and pos[m] < k then
              cout_avant:=cout_avant+card-MatCout[m,i];
              cout_apres:=cout_apres+card-MatCout[i,m];
          elif pos[m]=pos[i] then 
              cout_avant:=cout_avant+MatCout[i,m]+MatCout[m,i];
              cout_apres:=cout_apres+card-MatCout[i,m];
          elif pos[m]=k then
              cout_avant:=cout_avant+card-MatCout[m,i];
              cout_apres:=cout_apres+MatCout[i,m]+MatCout[m,i];
          fi;
       elif pos[i] > k then
          if pos[m] < pos[i] and pos[m] > k then
              cout_avant:=cout_avant+card-MatCout[i,m];
              cout_apres:=cout_apres+card-MatCout[m,i];
          elif pos[m]=pos[i] then 
              cout_avant:=cout_avant+MatCout[i,m]+MatCout[m,i];
              cout_apres:=cout_apres+card-MatCout[m,i];
          elif pos[m]=k then
              cout_avant:=cout_avant+card-MatCout[i,m];
              cout_apres:=cout_apres+MatCout[i,m]+MatCout[m,i];
          fi;
       fi;
    fi;
  od;  
  cout:=cout_apres-cout_avant;
  cout;
end:

Compute the cost of putting integer i in a new bucket after position k in ranking tri of [n]  (MatCout=cost_matrix(ens), pos=position(tri), card= cardinality of ens)

CoutNewPaquet:=proc(MatCout,card,pos,i,k,n)
  local res,temp,m,cout_avant,cout_apres,cout;
  cout_avant:=0;
  cout_apres:=0;
  for m from 1 to n do
    if m<>i then
       if pos[i] < k then
          if pos[m] > pos[i] and pos[m] < k+1 then
              cout_avant:=cout_avant+card-MatCout[m,i];
              cout_apres:=cout_apres+card-MatCout[i,m];
          elif pos[m]=pos[i] then 
              cout_avant:=cout_avant+MatCout[i,m]+MatCout[m,i];
              cout_apres:=cout_apres+card-MatCout[i,m];
          fi;
       elif pos[i] > k then
          if pos[m] < pos[i] and pos[m] > k then
              cout_avant:=cout_avant+card-MatCout[i,m];
              cout_apres:=cout_apres+card-MatCout[m,i];
          elif pos[m]=pos[i] then 
              cout_avant:=cout_avant+MatCout[i,m]+MatCout[m,i];
              cout_apres:=cout_apres+card-MatCout[m,i];
          fi;
       fi;
    fi;
  od;  
  cout:=cout_apres-cout_avant;
  cout;
end:

Compute the new ranking obtained from tri by putting i in bucket k  (pos=position(tri))

changePaquet:=proc(tri,pos,i,k)
  local posi,res,temp;
  res:=tri;
  posi:=pos[i];
  res[k]:=[op(res[k]),i];
  if nops(res[posi])=1 then
    if posi=1 then 
        res:=res[2..nops(tri)];
    elif posi=nops(tri) then
        res:=res[1..nops(tri)-1];
    else
        res:=[op(res[1..posi-1]),op(res[posi+1..nops(tri)])];
    fi;
  else
    temp:=convert(res[posi],set);
    res[posi]:=convert(temp minus {i},list);
  fi;
res;
end:

Compute the new ranking obtained from tri by putting i in a new bucket after bucket k  (pos=position(tri))

NewPaquet:=proc(tri,pos,i,k)
  local posi,res,temp,long,new,enlev;
  res:=tri;
  posi:=pos[i];
  long:=nops(tri[posi]);
  if long = 1 then
    if k < posi then
       res:=[op(tri[1..k]),tri[posi],op(tri[k+1..posi-1]),op(tri[posi+1..nops(tri)])];
    elif k > posi then
       res:=[op(tri[1..posi-1]),op(tri[posi+1..k]),tri[posi],op(tri[k+1..nops(tri)])];
    fi;
  else 
    new:=[i];
    enlev:=convert(res[posi],set) minus {i};
    res[posi]:=convert(enlev,list);
    if k <= posi then
      res:=[op(res[1..k]),new,op(res[k+1..posi]),op(res[posi+1..nops(tri)])];
    elif k > posi then
       res:=[op(res[1..posi]),op(res[posi+1..k]),new,op(res[k+1..nops(tri)])];
    fi;
   fi;
res;
end: