Friday, March 22, 2013

Knuth (Fisher-Yates) algorithm


/* microsoft
Write a function that gets a number n and prints out a random list
of numbers 1..n to the screen. For example:

randlist(5) : 1 5 3 2 4
randlist(6) : 4 6 1 5 3 2

This should be truly random (uniformly spread) and with a O(n) complexity.
Every number should appear only once. Random(n) is given as a tool you can use to generate a
single random number between 1-n */
//algorithm knuth suffle algo//
#include<stdio.h>
#include<stdlib.h>
int main()
{
int n,i=0,temp=0;
scanf("%d",&n);
int ar[n];
for(i=0;i<n;i++)
ar[i]=i+1;
while(i>0)
{
int r = rand()%i;//which is similar to ->rand()%i;
        temp = ar[i-1];
        ar[i-1] = ar[r];
        ar[r] = temp;
        i-=1;
}
for(i=0;i<n;i++)
printf("%d ",ar[i]);
return 0;
}

No comments:

Post a Comment