[SOLVED] 代写 C Computer Information Systems
COMP 150   Introduction to Programming   Instructor: Paul Rushton

Computer Information Systems
COMP 150   Introduction to Programming   Instructor: Paul Rushton
Project
Create a class that generates permutations of a set of symbols.

Requirements
•The class must be named PermutationGenerator.
•The PermutationGenerator class has two methods as follows.
hasNext
This method has no parameters.  It returns true if at least one permutation remains to be generated.
next
This method has no parameters.  It returns an array of the symbols (char[]) in a permutation (if any remain) or null otherwise.
•The following main method MUST be used, with NO CHANGES to test your class.
•public static void main(String[] args) {
•int count = 0;
•PermutationGenerator pg = new PermutationGenerator(new char[] { ‘R’, ‘E’, ‘G’, ‘A’, ‘L’ });
•while (pg.hasNext()) {
•count++;
•char[] permutation = pg.next();
•for (char symbol : permutation) System.out.print(symbol + ” “);
•System.out.println();
•}
•System.out.println(“Total permutations = ” + count);
}

Advice
One way to generate permutations is to repeatedly swap adjacent symbols until no more swaps are possible.  The following example for generating the permutations of the four symbols (‘A’, ‘B’, ‘C’, and ‘D’) should give you one idea.
Step
Description
Output
1
The first permutation is the initial list of symbols.
A B C D
2
Swap the first symbol (‘A’) with its right-hand neighbour.
B A C D
3
Swap ‘A’ with its right-hand neighbour.
B C A D
4
Swap ‘A’ with its right-hand neighbour.
B C D A
5
‘A’ has no right-hand neighbour.  Return it to it’s original position (the list becomes ‘A B C D’) and find the next symbol that can be swapped (start search at B).  ‘B’ can be swapped with its right-hand neighbour.
A C B D
6
Swap the first symbol (‘A’) with its right-hand neighbour.
C A B D
7
Swap the first symbol (‘A’) with its right-hand neighbour.
C B A D
8
Swap the first symbol (‘A’) with its right-hand neighbour.
C B D A
9
‘A’ has no right-hand neighbour.  Return it to it’s original position (the list becomes ‘A C B D’) and find the next symbol that can be swapped (start search at B).  ‘B’ can be swapped with its right-hand neighbour.
A C D B
10
Swap the first symbol (‘A’) with its right-hand neighbour.
C A D B
11
Swap the first symbol (‘A’) with its right-hand neighbour.
C D A B
12
Swap the first symbol (‘A’) with its right-hand neighbour.
C D B A
13
‘A’ has no right-hand neighbour.  Return it to it’s original position (the list becomes ‘A C D B’) and find the next symbol that can be swapped (start search at B).  ‘B’ cannot be swapped with its right-hand neighbour.  Return it to it’s original position (the list becomes ‘A B C D’) and find the next symbol that can be swapped (start search at C).  ‘C’ can be swapped with its right-hand neighbour.
A B D C
14
Swap the first symbol (‘A’) with its right-hand neighbour.
B A D C
15
Swap the first symbol (‘A’) with its right-hand neighbour.
B D A C
16
Swap the first symbol (‘A’) with its right-hand neighbour.
B D C A
17
‘A’ has no right-hand neighbour.  Return it to it’s original position (the list becomes ‘A B D C’) and find the next symbol that can be swapped (start search at B).  ‘B’ can be swapped with its right-hand neighbour.
A D B C
18
Swap the first symbol (‘A’) with its right-hand neighbour.
D A B C
19
Swap the first symbol (‘A’) with its right-hand neighbour.
D B A C
20
Swap the first symbol (‘A’) with its right-hand neighbour.
D B C A
21
‘A’ has no right-hand neighbour.  Return it to it’s original position (the list becomes ‘A D B C’) and find the next symbol that can be swapped (start search at B).  ‘B’ can be swapped with its right-hand neighbour.
A D C B
22
Swap the first symbol (‘A’) with its right-hand neighbour.
D A C B
23
Swap the first symbol (‘A’) with its right-hand neighbour.
D C A B
24
Swap the first symbol (‘A’) with its right-hand neighbour.
D C B A
25
‘A’ has no right-hand neighbour.  Return it to it’s original position (the list becomes ‘A D C B’) and find the next symbol that can be swapped (start search at B).  ‘B’ cannot be swapped with its right-hand neighbour.  Return it to it’s original position (the list becomes ‘A B D C’) and find the next symbol that can be swapped (start search at C).  ‘C’ cannot be swapped with its right-hand neighbour.  Return it to it’s original position (the list becomes ‘A B C D’) and find the next symbol that can be swapped (start search at D).  ‘D’ cannot be swapped with its right-hand neighbour.  Return it to it’s original position (the list becomes ‘A B C D’) and since there are no more symbols in the list then all permutations have been generated.

Marking
The project will be marked out of 10 based on the following principles.
•This project must be an individual effort.  Any apparent violation in your submitted work will be reported as Academic Misconduct.
•Recursion MUST NOT be used.
•The source code is well-designed and clearly understandable.
•The program is non-trivial and works correctly.
IF RECURSION IS USED OR
IF ANY OF THE FOLLOWING SUBMISSION REQUIREMENTS ARE NOT SATISFIED,
THE PROJECT MARK WILL BE RECORDED AS ZERO (0).
Submission Requirements
•Due date is October 30, 2019.
•The project must be entirely your own work.
•The submission rules must be followed.