/************************************************************************ ** ** NAME: partners.c ** ** DESCRIPTION: This code solves the 2-person partnering problem, which is: ** ** Assume you have n students. You would like to have lab ** sections in which these students choose partners ** to work together. Over the course of the semester, you'd ** like to have every student work with every other student ** exactly once. As there are n students, this can be done in ** n-1 days optimally. How is it done? (e.g. show how to pair ** 20 students up) ** ** AUTHOR: Dan Garcia - University of California at Berkeley ** Copyright (C) Dan Garcia, 1998. All rights reserved. ** ** DATE: 1998-09-23 ** ** TO COMPILE: unix% cc -o partners partners.c ** ** TO RUN: unix% ./partners ** ** EXAMPLE: unix% ./partners ** unix% ./partners v1.0 by Dan Garcia ** Enter the number of students to be paired up (must be even): 4 ** ** Partner Table (people on rows and columns, ** matrix contains day they meet) ** ** 2 3 4 ** +--------- ** 1| 1 2 3 ** 2| 3 2 ** 3| 1 ** ** Parsing the table into a useful form: ** ** Day 1:[1-2][3-4] ** Day 2:[1-3][2-4] ** Day 3:[1-4][2-3] ** ** UPDATE HIST: v1.0 - Release ** **************************************************************************/ #include #define VERSION "v1.0" #define AUTHOR "Dan Garcia " /************************************************************************ ** ** NAME: main ** ** DESCRIPTION: The starting point to the code. PrintHelloGetStudents ** gets the number of students, returns it to PrintPartners ** which prints the pairings. ** ************************************************************************/ main(argc,argv) int argc; char **argv; { PrintPartners(PrintHelloGetStudents(argv)); } /************************************************************************ ** ** NAME: PrintHelloGetStudents ** ** DESCRIPTION: Print Hello, then get the number of partners and return it. ** ************************************************************************/ PrintHelloGetStudents(argv) char **argv; { int p; printf("%s %s by %s\n",argv[0],VERSION,AUTHOR); printf("Enter the number of students to be paired up (must be even): "); scanf("%d",&p); if ((2 * (p / 2)) != p) { /* Not even */ printf("Sorry, p was not even...exiting.\n"); exit(1); } return(p); } /************************************************************************ ** ** NAME: PrintPartners ** ** DESCRIPTION: Print the way people should partner up so that everyone ** meets everyone else optimally. ** ************************************************************************/ PrintPartners(p) int p; { int p1,p2,r,c,day; int i,j; int *index, **m; /* Storage for the post-processing matrix */ index = (int *) malloc ((p-1) * sizeof(int)); m = (int **) malloc ((p-1) * sizeof (int *)); for(i=0;i