Lab 4: Generating Permutations, Program Input and the tar Command

Due: Wednesday, Sept. 24, 2014 @ 11:59 p.m.

Description:
This lab will be similar to Lab 3. You will implement an algorithm that generates 100 permutations of the numbers from 1 to n. A permutation is a sequence of numbers in which each number appears exactly once. In your program, you will write a function randperm() which will take an array (a[n]) and the value n as parameters and reorder a in place using the algorithm described below. In the main() function, you will read n, initialize a with numbers 1..n and call randperm(a, n) 100 times. After each call to randperm(), you will print a.

Background Preparation: 
Read the manual page for the tar command. Review in your textbook how to read keyboard input into your program. Continue your work learning about editing with vi/vim, general Unix commands and transferring files to and from Mason and/or Zeus.
Generating Permutations:
You will use the random number generator functions srandom() and random().  You will seed the random number generator like you did with Lab 3, by using the last four digits of your G number as the token of a #define pre-processor statement.

You will then ask the user to input the desired value for n and read the response using a fgets/sscanf combination of statements.

Since your program will generate integer values in the range 1..n, you must normalize the result of a call to the random() function using the following formula:

        int my_random_val = random()%n + 1;

(Note that in Lab 3, you used srand() and rand(). The random() function is considered to be of higher quality. However, also note that random() returns a long int value whereas rand() returns an int value. This is not an issue for the statement given above since you are using the modulo operation.)

The Perfect Shuffle:
The algorithm you will use to generate permutations is the Fisher-Yates shuffle, also called the "Perfect Shuffle" algorithm.  It works as follows:

void randperm(int *a, const int n)
// Shuffles an array a of n elements (indices 0..n-1):
  for i from n − 1 downto 1 do
       j ← random integer with 0 ≤ j ≤ i
       exchange a[j] and a[i]

Specifications:
Your program will start by printing an informational message, stating your name, lab section, and what the program will do.

It will declare in main() a local array a that holds 200 values of type int.

It will seed the random number generator as described in Lab 3.

It will then ask the user for an integer greater than 0 and less than 200. It will read the number from the stdin input stream. If the user does not enter a proper value, the program will prompt the user again until a proper value is entered.

The program will then perform the following 100 times using a loop:

  1. Call a function that initializes a with the numbers from 1 to n. Any part of array a that is beyond n is left uninitialized.
  2. Call randperm() to generate a permutation of the numbers from 1 to n.
  3. After returning from randperm(), the list of n numbers is printed to the screen.

Your program will not use any global variables.

Any constants used in the program (200, 100, your G#, etc.) will be given as #define macros.

You will compile your program with a Makefile using the gcc compiler. You may edit your Makefile from Lab 3.

Testing:
Test your program to ensure that each iteration produces a distinct permutation. Make sure that the program output is neat and readable. During testing, you may want to use smaller values for the input value n to avoid the text wrapping and making it difficult to compare the various permutations that were generated. Also make sure that your code is neat, with consistent indenting and good comments.

Dividing the program:
Once you are sure that your program is working correctly, you will divide the source file into three distinct source/header files:
  1. The file that contains the main function: Lab4.c
  2. The file that contains your initialization function and randperm(): Lab4_lib.c
  3. A header file (Lab4.h) that contains your #defines and function prototypes. Note that you will need to have Lab4.c and Lab4_lib.c include this header file.
You will also need to modify your Makefile so that it can compile the program given the three separate source and header files.

Submission:

Log in to mason or zeus and copy your program's files into a directory named Lab4. Start a typescript session in the directory above Lab4. Type "uname -a" to show that you are on mason or zeus. Change to the Lab4 directory and use the cat command to list all your source files and Makefile. Compile your program using the make command. Run your program to show that it executes correctly. 

Change back to the directory immediately above Lab4, and use the tar command to create an archive of all the files in the Lab4 directory. Name this archive Lab4.tar. Re-read the man page if necessary to discover the proper options to use. [NOTE: Should we add the z option to create a gzip file?]

Finally, exit the typescript session by typing crtl-d.

Verify that your script file was created correctly by using the more (or less) command (your choice) to see the contents of the file. As always, information on these commands can be obtained by using the manual pages ("man more" or "man less"). Once you are sure the file is correct, copy the script file and Lab4.tar back to your local computer and submit both of them to Blackboard as Lab 3.