Skip to content

Instantly share code, notes, and snippets.

@dufferzafar

dufferzafar/MinDistArray.c

Last active Aug 29, 2015
Embed
What would you like to do?
Finding an array that is at minimum distance from a group of arrays.
# include <stdio.h>
# include <stdlib.h>
# include <time.h>
# include <math.h>
float distance(int *, int *, int);
void printArr(int *, int, int, char *);
void printMat(int **, int, int, char *);
int main(int argc, char const *argv[])
{
int i, j, k, rnd;
int nSize, nPerms;
int *univ, **perm, **pos;
int tempSum;
int tempMin, tempPos;
int *sum, *ansp, *ans;
float tempDist, finalDist;
srand(time(0));
printf("\nEnter size of array: "); scanf("%d", &nSize);
printf("\nEnter number of permutations: "); scanf("%d", &nPerms);
univ = (int *)malloc(nSize * sizeof(int));
perm = (int **)malloc(nPerms * sizeof(int *));
for (i = 0; i < nPerms; i++)
perm[i] = (int *)malloc(nSize * sizeof(int));
pos = (int **)malloc(nPerms * sizeof(int *));
for (i = 0; i < nPerms; i++)
pos[i] = (int *)malloc(nSize * sizeof(int));
sum = (int *)malloc(nSize * sizeof(int));
ansp = (int *)malloc(nSize * sizeof(int));
ans = (int *)malloc(nSize * sizeof(int));
for (i = 0; i < nSize; i++)
univ[i] = i+1;
for (i = 0; i < nPerms; i++)
{
for (j = 0; j < nSize; j++)
{
// Random number between 0 and j
rnd = (j == 0) ? 0 : (rand() % (j+1));
if (rnd != j)
perm[i][j] = perm[i][rnd];
perm[i][rnd] = univ[j];
}
}
// printMat(perm, nPerms, nSize, "Permutation");
for (i = 0; i < nPerms; i++)
{
for (j = 1; j <= nSize; j++)
{
for(k = 0; k < nSize; k++)
{
if (j == perm[i][k])
break;
}
pos[i][j-1] = k+1;
}
}
// printMat(pos, nPerms, nSize, "Position");
for (j = 0; j < nSize; j++)
{
tempSum = 0;
for (i = 0; i < nPerms; i++)
{
tempSum += pos[i][j];
}
sum[j] = tempSum;
}
// printArr(sum, nSize, 0, "Sum ");
for(i = 0; i < nSize; i++)
{
tempMin = sum[i]; tempPos = i;
for (j = 0; j < nSize; j++)
{
if (sum[j] < tempMin)
{
tempMin = sum[j];
tempPos = j;
}
}
ansp[i] = tempPos; sum[tempPos] = RAND_MAX;
}
// printArr(ansp, nSize, 1, "AnswerP ");
for(i = 0; i < nSize; i++)
ans[ansp[i]] = i+1;
printArr(ans, nSize, 0, "Answer ");
printf("\n\n");
finalDist = 0;
for(i = 0; i < nPerms; i++)
{
tempDist = distance(ans, pos[i], nSize);
finalDist += tempDist;
}
printf("\n\nThe distance of answer from all permutations is: %f \n", finalDist/nPerms);
return 0;
}
float distance(int *arr1, int *arr2, int size)
{
int i = 0;
float dist = 0;
for(i = 0; i < size; i++)
dist += abs(arr1[i] - arr2[i]);
return (dist / (0.5 * size * (size)));
}
void printArr(int *arr, int size, int adj, char *str)
{
int i;
printf("\n%s \t: ", str);
for (i = 0; i < size; i++)
{
printf("%3d ", arr[i] + adj);
}
}
void printMat(int **mat, int row, int col, char *str)
{
int i, j;
printf("\n");
for (i = 0; i < row; i++)
{
printf("%s %d\t: ", str, i+1);
for (j = 0; j < col; j++)
printf("%3d ", mat[i][j]);
printf("\n");
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment