// Iterative analysis of self-organizing lists for various distributions
//     and strategies.
// Summer 2004 Lab 1

#include <stdio.h>
#include <math.h>

#define MAXN (8)
#define MAXNFACT (8*7*6*5*4*3*2)

int n,nfact;
int columnValue[MAXN];
float eps;
int maxIterations;

int cardPermset()
{
int i,card;

columnValue[n-1]=1;
for (i=n-2;i>=0;i--)
  columnValue[i]=columnValue[i+1]*(n-i-1);
card=n*columnValue[0];
/*
printf("column values: ");
for (i=0;i<n;i++)
  printf("%d ",columnValue[i]);
printf("\n");
printf("cardinality of permutation set %d\n",card);
*/
return card;
}

void rank2perm(int rank,int perm[MAXN])
{
int i,j;
int r[MAXN],available[MAXN];

for (i=0;i<n;i++)
{
  r[i]=rank/columnValue[i];
  rank=rank%columnValue[i];
}

for (i=0;i<n;i++)
  available[i]=i;
for (i=0;i<n;i++)
{
  perm[i]=available[r[i]];
  for (j=r[i];j<n-1-i;j++)
    available[j]=available[j+1];
}
}

int perm2rank(int perm[20])
{
int i,j,rank;
int available[20],r[20];

for (i=0;i<n;i++)
  available[i]=i;
for (i=0;i<n;i++)
{
  for (j=0;perm[i]!=available[j];j++)
    ;
  r[i]=j;
  for (;j<n-1-i;j++)
    available[j]=available[j+1];
}
rank=0;
for (i=0;i<n;i++)
  rank+=r[i]*columnValue[i];
return rank;
}

int strategyNum,distNum;
double dist[MAXN],prob[2][MAXNFACT];
int oldProb=0,newProb=1;
// If an access to element i at position j
// causes change from state k to state p, then
// predRank[p][j]=k and predAccessed[p][j]=i.
int predRank[MAXNFACT][MAXN];
char predAccessed[MAXNFACT][MAXN];

void printModelByPerms()
{
int i,j,p,perm[MAXNFACT];

printf("By perms:\n");
for (i=0;i<nfact;i++)
{
  printf("P");
  rank2perm(i,perm);
  for (p=0;p<n;p++)
    printf("%d",perm[p]);
  printf("<-");
  for (j=0;j<n;j++)
  {
    printf("p%d*P",predAccessed[i][j]);
    rank2perm(predRank[i][j],perm);
    for (p=0;p<n;p++)
      printf("%d",perm[p]);
    if (j<n-1)
      printf("+");
  }
  printf("\n");
}
}

void printModelByRanks()
{
int i,j;

printf("By ranks:\n");
for (i=0;i<nfact;i++)
{
  printf("P%d<-",i);
  for (j=0;j<n;j++)
  {
    printf("p%d*P%d",predAccessed[i][j],predRank[i][j]);
    if (j<n-1)
      printf("+");
  }
  printf("\n");
}
}

void iterativeSolver()
{
int i,j,p,perm[MAXNFACT];

// Initial probabilities
for (i=0;i<nfact;i++)
  prob[oldProb][i]=1.0/nfact;
// Compute new probabilities based on old probabilities
for (i=0;i<maxIterations;i++)
{
/*
  printf("Start of iteration %d\n",i);
  for (j=0;j<nfact;j++)
  {
    rank2perm(j,perm);
    for (p=0;p<n;p++)
      printf("%d",perm[p]);
    printf(": %f\n",prob[oldProb][j]);
  }
*/
  for (j=0;j<nfact;j++)
  {
    prob[newProb][j]=0.0;
    for (p=0;p<n;p++)
      prob[newProb][j]+=prob[oldProb][predRank[j][p]]*dist[predAccessed[j][p]];
  }
  oldProb=1-oldProb;
  newProb=1-newProb;
  for (j=0;j<nfact;j++)
    if (fabs(prob[newProb][j]-prob[oldProb][j])>eps)
      break;
  if (j==nfact) // All probabilities had change bounded by eps
    break;
}
printf("Used %d iterations\n",i+1);
if (n<=4) // Dump probabilities for small cases.
  for (i=0;i<nfact;i++)
  {
    rank2perm(i,perm);
    printf("%f: ",prob[oldProb][i]);
    for (j=0;j<n;j++)
      printf("%d",perm[j]);
    printf("\n");
  }
}

void determineProbes()
{
double probes=0.0,work;
int i,j,perm[MAXN];
double elementProbes[MAXN];

for (i=0;i<n;i++)
  elementProbes[i]=0.0;

for (i=0;i<nfact;i++)
{
  work=0.0;
  rank2perm(i,perm);
  for (j=0;j<n;j++)
  {
    work+=(j+1)*dist[perm[j]];
    elementProbes[perm[j]]+=prob[oldProb][i]*(j+1);
  }
  probes+=prob[oldProb][i]*work;
}
printf("Expected probes is %f\n",probes);
for (i=0;i<n;i++)
  printf("Element %d expected probes %f\n",i,elementProbes[i]);
}

main()
{
int i,j,perm[MAXN],temp;
double Hn;

printf("Enter n strategy (MTF/trans) dist (uni/Zipf) iterations epsilon\n");
scanf("%d %d %d %d %f",&n,&strategyNum,&distNum,&maxIterations,&eps);

nfact=cardPermset();
if (strategyNum==0)
{
  printf("Move-to-front\n");
  for (i=0;i<nfact;i++)
  {
    rank2perm(i,perm);
    predRank[i][0]=i; // access is to first element
    predAccessed[i][0]=perm[0];
    for (j=1;j<n;j++)
    {
      perm[j-1]=perm[j];
      perm[j]=predAccessed[i][0];
      predRank[i][j]=perm2rank(perm);
      predAccessed[i][j]=predAccessed[i][0];
    }
  }
}
else
{
  printf("Transpose\n");
  for (i=0;i<nfact;i++)
  {
    rank2perm(i,perm);
    predRank[i][0]=i; // access is to first element
    predAccessed[i][0]=perm[0];
    for (j=1;j<n;j++)
    {
      rank2perm(i,perm);
      temp=perm[j-1];
      perm[j-1]=perm[j];
      perm[j]=temp;
      predRank[i][j]=perm2rank(perm);
      predAccessed[i][j]=perm[j];
    }
  }
}

if (distNum==0)
{
  printf("Uniform\n");
  for (i=0;i<n;i++)
    dist[i]=1.0/n;
}
else
{
  printf("Zipf\n");
  Hn=0.0;
  for (i=1;i<=n;i++)
    Hn+=1.0/i;
  for (i=0;i<n;i++)
    dist[i]=1.0/((i+1)*Hn);
}

/*
printModelByPerms();
printModelByRanks();
*/

iterativeSolver();
determineProbes();
}