1

Hi everyone,

My program is doing what it suppose to do, except that it generates a loop with the answer.

...
ERROR in uniform.discrete_uniform(): a=100 b=99
ERROR in uniform.discrete_uniform(): a=100 b=99
ERROR in uniform.discrete_uniform(): a=100 b=99
ERROR in uniform.discrete_uniform(): a=100 b=99
ERROR in uniform.discrete_uniform(): a=100 b=99
ERROR in uniform.discrete_uniform(): a=100 b=99
ERROR in uniform.discrete_uniform(): a=100 b=99
ERROR in uniform.discrete_uniform(): a=100 b=99
ERROR in uniform.discrete_uniform(): a=100 b=99
ERROR in uniform.discrete_uniform(): a=100 b=99
ERROR in uniform.discrete_uniform(): a=100 b=99
ERROR in uniform.discrete_uniform(): a=100 b=99
ERROR in uniform.discrete_uniform(): a=100 b=99
ERROR in uniform.discrete_uniform(): a=100 b=99
ERROR in uniform.discrete_uniform(): a=100 b=99
ERROR in uniform.discrete_uniform(): a=100 b=99
ERROR in uniform.discrete_uniform(): a=100 b=99
ERROR in uniform.discrete_uniform(): a=100 b=99
ERROR in uniform.discrete_uniform(): a=100 b=99
ERROR in uniform.discrete_uniform(): a=100 b=99
ERROR in uniform.discrete_uniform(): a=100 b=99
...

Can anyone help me?

I have attached the files necessary to run the program.

Thanks

Attachments
#include <stdio.h>
#include <stdlib.h>

/* Step 1: define your struct here */
typedef struct _Node {
  int data1, data2;
  struct _Node* next;
  struct _Node* next2;
} Node;

typedef struct _List {
  Node* front;
  Node* front2;
  Node* rear;
  Node* rear2;
} List;

static List list;

/* Step 2: put code in the functions below to make the list work. */

void clearList ()
{
  while (list.front)
  {
    Node* tmp = list.front;
    list.front = list.front->next;
    free(tmp);
  }

  list.front = list.front2 = list.rear = list.rear2 = NULL;
}

void addData1(Node* newNode, int data1)
{
  Node* prev = NULL;
  Node* iter = list.front;

  newNode->data1 = data1;

  while (iter && iter->data1 < data1)
  {
    prev = iter;
    iter = iter->next;
  }
  
  if (list.front == NULL)
  {
    list.front = list.rear = newNode;
    newNode->next = NULL;
  }
  else
    if (prev == NULL)
    {
      newNode->next = list.front;
      list.front = newNode;
    }
    else {
      newNode->next = iter;
      prev->next = newNode;
      if (prev == list.rear)
        list.rear = newNode;
    }
}

void addData2(Node* newNode, int data2)
{
  Node* prev = NULL;
  Node* iter = list.front2;

  newNode->data2 = data2;
  while (iter && iter->data2 < data2)
  {
    prev = iter;
    iter = iter->next2;
  }
  
  if (list.front2 == NULL)
  {
    list.front2 = list.rear2 = newNode;
    newNode->next2 = NULL;
  }
  else
    if (prev == NULL)
    {
      newNode->next2 = list.front2;
      list.front2 = newNode;
    }
    else {
      newNode->next2 = iter;
      prev->next2 = newNode;
      if (prev == list.rear2)
        list.rear2 = newNode;
    }
}

void addToList (int data1, int data2)
{
  Node* newNode = (Node*)malloc(sizeof(Node));

  addData1(newNode, data1);
  addData2(newNode, data2);
}

void printFirst ()
{
  Node* iter = list.front;

  while (iter)
  {
    printf("(%d %d)\n", iter->data1, iter->data2);
    iter = iter->next;
  }
}

void printSecond ()
{
  Node* iter = list.front2;

  while (iter)
  {
    printf("(%d %d)\n", iter->data1, iter->data2);
    iter = iter->next2;
  }
}

int findPos2(int data1, int data2)
{
  int pos = 0;
  Node* iter = list.front2;

  while (iter && !(iter->data1 == data1 && iter->data2 == data2))
  {
    ++pos;
    iter = iter->next2;
  }

  return pos;
}

int disparity ()
{
  int result = 0;
  Node* iter = list.front;
  int pos = 0;

  while (iter)
  {
    result += abs(findPos2(iter->data1, iter->data2) - pos);

    iter = iter->next;
    ++pos;
  }

  return result;
}
#include <stdio.h>
#include <math.h>
#include <string.h>

#define boolean int
#define FALSE 0
#define TRUE 1

/* These are the functions implemented in the linked list code */
extern void clearList ();
extern void addToList (int,int);
extern void printFirst ();
extern void printSecond ();
extern int disparity ();

/* This is needed for random generation */
extern discrete_uniform (int, int);

void permute (int *A, int n)
{
  int i = 0;
  for (i=0; i<n; i++) {
    /* Pick a random element to move to i-th position. */
    int k = discrete_uniform (i+1, n-1);
    int temp = A[i];
    A[i] = A[k];
    A[k] = temp;
  }
}

void addElements (int n)
{
  int i;
  int *perm1, *perm2;

  /* First, make two random permutations. */
  perm1 = (int*) malloc (sizeof(int) * n);
  perm2 = (int*) malloc (sizeof(int) * n);
  for (i=0; i<n; i++) {
    perm1[i] = perm2[i] = i;
  }
  permute (perm1, n);
  permute (perm2, n);
    
  for (i=1; i<=n; i++) {
    addToList (perm1[i], perm2[i]);
  }
}


void test (char *testName, int numTrials, int listSize, boolean printList)
{
  double totalDisp, avgDisp;
  int n;

  /* Repeat over a number of trials and estimate average. */
  totalDisp = 0;
  for (n=0; n<numTrials; n++) {
    clearList ();
    addElements (listSize);
    totalDisp += disparity ();
  }

  printf ("-----------------------\n");
  printf ("%s\n", testName);
  if (printList) {
    printFirst ();
    printSecond ();
  }
  printf("Average disparity: %lf\n", (totalDisp/numTrials));

}

int main (int argc, char **argv) 
{
  // Simple tests.
  test ("Test 1: 1 element", 1, 1, TRUE);
  test ("Test 2: 5 elements", 1, 5, TRUE);
  test ("Test 3: 10 elements", 1, 10, TRUE);

  // Statistics.
  test ("Test 4: 10 elements", 10000, 10, FALSE);
  test ("Test 5: 100 elements", 10000, 100, FALSE);
}
#include <stdio.h>
#include <math.h>


static long r_seed = 12345678L;

/* Uniform [0,1] using the standard Lehmer generator. 
   See http://www.seas.gwu.edu/~simhaweb/java/lectures/appendix/random.html
   for more details. */

double uniform ()
{
  static long m = 2147483647;
  static long a = 48271;
  static long q = 44488;
  static long r = 3399;
  long t, lo, hi;

  hi = r_seed / q;
  lo = r_seed - q * hi;
  t = a * lo - r * hi;
  if (t > 0)
    r_seed = t;
  else
    r_seed = t + m;
  return ( (double) r_seed / (double) m );
}



/* Uniform random number generator - returns a number between a and b */ 

double uniform_range (double a, double b)
{
  if (b > a)
    return ( a + (b-a) * uniform() );
  else { 
    printf ("ERROR: in uniform.uniform_range(): a=%lf b=%lf\n",a,b); return 0;
  }
}



/* Uniform random number generator - returns an integral number between a and b */ 

long discrete_uniform (long a, long b)
{
  if (b > a) {
    double x = uniform ();
    long c = ( a + (long) floor((b-a+1)*x) );
    return c;
  }
  else if (a == b) return a;
  else { printf("ERROR in uniform.discrete_uniform(): a=%2ld b=%2ld\n",a,b);return 0;}
}



/* Generate a random int from the given discrete pmf */

int generateFromPmf (double *pmf, int length)
{
  int lastIndex, i;
  double u, sum;

  if ( ( pmf == NULL) || (length <= 1) ){
    printf ("ERROR: in uniform.generateFromPmf(): pmf null or zero-length");
    return 0;
  }
    
  lastIndex = length - 1;
  u = uniform();
  i = 0;
  sum = pmf[0];
  while ( (i < lastIndex) && (u > sum) ) {
    i++;
    sum += pmf[i];
  }
  return i;
}



/* Generate from zipf distribution of given size. */

int zipf (int size) 
{
  double *pmf, sum;
  int index, i;

  pmf = (double*) malloc (sizeof(double)*(size+1));
  sum = 0;
  pmf[0] = 0;
  for (i=1; i<=size; i++) {
    pmf[i] = 1.0 / (double) i;
    sum += pmf[i];
  }
  for (i=1; i<=size; i++) {
    pmf[i] = pmf[i] / sum;
  }
  index = generateFromPmf (pmf, size+1);
  if (index == 0)
    index = 1;
  return index;
}



/* Reverse zipf, has an increasing pmf */

int reverseZipf (int size) 
{
  double *pmf, sum;
  int index, i;

  pmf = (double*) malloc (sizeof(double)*(size+1));
  pmf[0] = 0;
  sum = 0;
  for (i=1; i<=size; i++) {
    pmf[i] = 1.0 / (double) (size-i+1);
    sum += pmf[i];
  }
  for (i=1; i<=size; i++) {
    pmf[i] = pmf[i] / sum;
  }
  index = generateFromPmf (pmf, size+1);
  if (index == 0)
    index = 1;
  return index;
}
2
Contributors
2
Replies
3
Views
8 Years
Discussion Span
Last Post by Samyx
0

If your return value for the error condition is not checked, why would the loop break?

void permute (int *A, int n)
{
  int i = 0;
  for (i=0; i<n; i++) {
    /* Pick a random element to move to i-th position. */
    int k = discrete_uniform (i+1, n-1);
    int temp = A[i];
    A[i] = A[k];
    A[k] = temp;
  }
}

Edited by Dave Sinkula: n/a

1

Thank you, problem fixed!

int k = discrete_uniform (i, n-1);
This question has already been answered. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.