Homework 4

Due in class on Friday, February 18.

Turn in a HARDCOPY of your source code with your NAME and STUDENT ID.

Problem: Permutations

Define, for our purposes, a permutation of a set to be some ordering of the members of that set. For instance, there are six permutations of the set { A, B, C }:

ABC
ACB
BAC
BCA
CAB
CBA

Write a program which accepts as input a positive integer n and prints out all permutations of the first n positive integers.

Here's a sample interaction with my program:

Enter n: 3
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

And, here's yet another sample interaction with my program:

Enter n: 4
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1

Problem: Latin Squares

A n-by-n Latin Square is a n-by-n array of integers such that every entry is one of the first n positive integers, and no integer appears more than once in each row and column. As an example,

1 2 3 4 5
2 1 4 5 3
3 4 5 1 2
4 5 2 3 1
5 3 1 2 4

is a 5-by-5 Latin Square; every entry is one of the first 5 positive integers (1, 2, 3, 4, 5) and no integer appears more than once in each row and column.

Write a program which accepts as input a positive integer n (assumed to be greater than 2) and prints out all n-by-n Latin Squares. (It is the case that for all n greater than 2, there is more than one n-by-n Latin Square.)

Here's a sample interaction with my program:

Enter n: 3

1 2 3 
2 3 1 
3 1 2 

1 2 3 
3 1 2 
2 3 1 

1 3 2 
2 1 3 
3 2 1 

1 3 2 
3 2 1 
2 1 3 

2 1 3 
1 3 2 
3 2 1 

2 1 3 
3 2 1 
1 3 2 

2 3 1 
1 2 3 
3 1 2 

2 3 1 
3 1 2 
1 2 3 

3 1 2 
1 2 3 
2 3 1 

3 1 2 
2 3 1 
1 2 3 

3 2 1 
1 3 2 
2 1 3 

3 2 1 
2 1 3 
1 3 2