program generates a set U of n random numbers , and then generates m random permutations of this set. Our objective is to find a set S , such that the distance of this set S from all sets L[i] is minimum .

setdistance.c

/*
* The following program generates a set U of n random numbers , and then generates m random permutations of this set.
* Our objective is to find a set S , such that the distance of this set S from all sets L[i] is minimum .
*
* The distance between two arrays A and B is given by:
*
*  distance = 0
*  for i = 1 to N do:
*     distance = distance + | position of element i in set A - position of element i in set B |
*
*  The distance can be [0,1] normalized by dividing it by 0.5 * (n^2)
*/

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

//our very own data type , stores values and the mean of their position(s) in the m lists
typedef struct intfloat {
    int key ;
    float pos ;
}intfloat;

//prototyping , functioning explained in context of usage
int inList(intfloat * U,int num,int limit);
int getPos(int* L,int key,int n);
float distance(int* l,int * L,int n);

int main(void)
{
    int i,j,num=0,min=0;
    int m,n,rnd=0;
    float meandist=0,tempdist=0;
    intfloat * U ;
    int ** L ;
    int * bro; // the bro of all lists , we're trying to "generate" it 
    
	printf("Enter the value of m :");
	scanf("%d",&m);
	printf("Enter the value of n : ");
	scanf("%d",&n);
	
	srand(7);
	
	U = (intfloat*)malloc(sizeof(intfloat) * n );
	for ( i=0 ; i < n ; i++)
	    U[i].pos = 0;
	
	L = (int**)malloc(sizeof(int*) * m );
	
	for ( i=0 ; i < m ; i++ )
	{
	    L[i] = (int*)malloc(sizeof(int) * n );
	}
	bro = (int*)malloc(sizeof(int) * n );
	//generating the universal set U of n random numbers
	
	for ( i=0 ; i < n ;)
	{
	    if ( !inList(U,(num = rand() % 100 ),i) )
	        U[i++].key = num ;
	}
	
	/* 
	*    Everyday i'm shufflin' 
	*    (The knuth-fisher-yates random shuffle,inside-out method used to produce copies)
	*/
	
	for  ( i=0 ; i < m ; i++)
	{
	    for ( j=0 ; j < n ; j++)
	    {
	        rnd = rand() % (j+1);
	        
	        if ( rnd != j)
	            L[i][j] = L[i][rnd];
	            
	        L[i][rnd] = U[j].key;
	        U[j].pos += rnd ; 
	    }
	}
	
	//printing the universal set
	printf("U:{ ");
	for ( i=0 ; i < n ; i++ )
	{
	    printf("%d ",U[i].key);
	}
	printf("}\n");

	//now generate the bro list
	for ( i=0 ; i < n ; i++)
	{
	    min = i;
	    for ( j=i ; j < n ; j++)
	    {
	        if ( U[j].pos < U[i].pos)
	            min = j;
	    }
	    bro[i] = U[min].key ;
	    U[min].key = U[i].key ;
	    U[min].pos = U[i].pos ;
	}
		
	//printing the lists 
	printf("The m lists are : \n");
	for ( i=0 ; i < m ; i++)
	{
	    printf("L[%d]: { ",i+1);
	    for ( j=0 ; j < n ; j++)
	    {
	        printf("%d ",L[i][j]);
	    }
	    printf("}\n");
	}	
	
	//printing the bro list. and its distance from each list .
	printf("The list with the minimum distance from all: {");
	for ( i=0 ; i < n ; i++ )
	{
	    printf("%d ",bro[i]);
	}
	printf("}\n");
	
	for ( i=0 ; i < m ; i++)
	{
	    tempdist = distance(bro,L[i],n); //just because we don't want to call our function twice
	    printf("distance(l,L[%d]) : %f\n",i+1,tempdist);
	    meandist += tempdist ;
	}
	
	meandist /= m;
	
	printf("The mean distace of l from all lists L[i]: %f\n",meandist);
	return 0;
}

int inList(intfloat * U,int num,int limit)
{
    int i;
    for ( i=0 ; i < limit ; i++)
    {
        if ( U[i].key == num )
            return 1;
    }   
    return 0;
}

float distance(int* l,int * L,int n)
{
    float sum=0;
    int i=0 ;
    
    for ( i=0 ; i < n ; i++)
    {
        sum += abs(i - getPos(L,l[i],n) ) ;   //position of ith element in list l
    }
    
    sum /= 0.5*n*n ;
    return sum ;
}

//function to search for position of ith element of list l in list L
int getPos(int* L,int key,int n)
{
    int j=0;
    //linear searching in the unsorted array
    for(j=0 ; j < n ; j++)
    {
        if ( L[j] == key )
            return j;
    }

    return 0;
}