Mathematics 152
Programming Project #1
      A C++ Program to Multiply Permutations -- Linux version

Revised: September 23, 2003

These instructions assume that you have never used KDevelop before and that you may have only limited experience with programming in  C++.
You will create a C++ program that lets you specify two permutations like a = (123) and b= (14)(35), form the products a*b and b*a, and compute and display all the powers of a, b and the two products.  For the user-interface parts of the program, you need only follow instructions, but
you will have to implement the "real mathematics" yourself.

KDevelop is installed on all the Linux machines in the Science Center basement, found in the room on the left as you go down the main stairs.  This project has been done successfully on those machines, but there is always the risk that the networked installation of Linux has been changed in a way that causes trouble.  If you followe instructions carefully and hit a mysterious bug, contact Paul Bamberg to check out the situation.

If you like KDevelop and have 4GB free on your hard drive, you can install Linux.  It's free.

In building this program you will learn the following features of  C++ under Linux and KDevelop:
Widget-based applications -- the simplest type, but all you are likely to need.
Push Buttons -- the simplest way to control a program interactively.
Line Edit widgets - the easiest way to display single numbers or strings of  text.
Text labels and group boxes -- for identifying what your line edits are displaying.
List boxes -- a convenient way to display many steps of a calculation.
QString variables -- the simple way to hold text.

There are two stages in building the application.
Stage 1. Create a widget-based application and lay out the controls you want.  This does not require you to write any code.  You just use a program-writing tool called an application wizard and a graphical dialog editor called Qt Designer.  At the end of this stage you will have a working C++ program and will be able to see what your finished application looks like.

Stage 2. Write the definitions of the C++ functions in your program.  This is where the mathematics comes in.  As you do this, you will probably want to add a few more functions of your own that are not connected with buttons and a few more variables that are not connected with line edits.

In the new terminal room are a large number of computers with Red Hat Linux 7.3 installed.  You can use your FAS account name and password to log in.  If you have 3 GB free on a defragmented hard drive have would like to install Linux on your own computer, send email to to make arrangements.

0. If you have not already done so, create a link to KDevelop 2.1 on the desktop.  The way to do this is to click the leftmost icon, with the 6-toothed gear and the large "K," from the K Panel to bring up the main menu.  Select Development...KDevelop 2.1.  Left-click and drag onto the desktop, and select Link Here.

1. Click the KDevelop icon and close the "Tip of the Day."  From the main menu, select Project...New.  The Application Wizard drops down.  In the tree on the left, click the + next to KDE, then click KDE 2 Mini from the list that drops down. Click the Next Button.

2. Now you see the Generate Settings dialog.  For a project directory, navigate to a subdirectory of your home directory, and within this choose a new subdirectory named "proj_permute."  An example project directory might be /home/paulb/math102/projects/proj_permute.  Enter Permute as the project name.  The Author and Email fields should have been filled in automatically from when you configured KDevelop. Below, uncheck everything except "generate sources and headers."  Click Create.  Wait until you see the "READY" message, then click Exit.  At the top of the left panel, click the Classes tab.  You will see a class Permute.

3. Select File...New from the menu or click the New icon at the left of the toolbar, and choose Qt Designer File (.ui).  Type in "permutebase" as the filename; the .ui will be added automatically.  Leaving "use Template" and "add to Project" checked, click OK.  Respond "No" to "Do you want to load it as ASCII file?"  When the New Form dialog pops up, choose Widget and click OK.  Under Properties, change the name from Form1 to PermuteBase.  Use File...SaveAs.. to save the form, and be sure to navigate down to the directory named permute under your project, for example /home/paulb/S45/homework/proj_permute/permute.  You should already see permutebase in this directory -- overwrite it.  Close Qt Designer.

4. Select Build..Make (or press F8) to build the project.  After a while you will see the message ***success***.  Select Project...Add Existing Files....  For source files, navigate down to the  permute directory and select the file permutebase.h, which was created during the build process.  Do not also select permutebase.cpp, or you will get linker errors! Click OK twice. Now you should see PermuteBase under the Classes tab, along with Permute.  You should regard the class PermuteBase as "read-only" since it will be rebuilt every time you edit permutebase.ui, and any changes that you made would be lost.  When the file permutebase.h is rebuilt, you will need to reload it into the editor.  You may be asked about this when you right-click on PermuteBase.

5. Right click the Permute class and choose Goto declaration.  Change the first line to
class Permute: public PermuteBase.
Above this, change
#include <qwidget.h>
#include "permutebase.h"

6. Click the + next to Permute, and click the constructor.
Replace the second occurrence of QWidget by PermuteBase to get
Permute::Permute(QWidget *parent, const char *name) : PermuteBase(parent, name).
Press F8 to rebuild the project, and you should see *** success ***
When you press F9, the project should run, showing you a blank form.

7. You will continue by adding widgets to the form.  An easy way to do this is to select Tools...Qt Designer, then choose File... Recently opened files.  Your file permutefile.ui will be at the bottom of the list, and you can select it to open.  Alternatively, under the Files tab, you can double-click permutebase.ui and answer No to "Do you want to load it as ASCII file?"
Change the caption to Multiplying Permutations.
Click the + next to font. Change the Family to Lucidatypewriter and the Point Size to 12. (This step used to cause problems in the Science Center, and then the problems went away.  You can skip it if you want to play safe)

All the widgets that you will need are on the same row as the icon that shows an "OK" button.  Find this Push Button, and notice how a tooltip pops up if you hold the mouse over it for a while.  Four icons to the right, locate the Group Box.  Four icons to the right of that is the List Box.  Seven more to the right, with "ab|", is the Line Edit.
Finally, at the left of the next row, with a big A, is the Text Label.  With these widgets and the Combo Box (6 to the right of the Line Edit) you can build a lot of useful applications.

8. Start with a Group Box at the upper left: click the group box icon, place the crosshair cursor where you want the upper left corner to be, and stretch it out to about 200 pixels wide and 250 pixels high.  Under Properties, change the title to Permutations.

9. In the upper left of the group box, place a Text Label,.  Change the text to "a" and the halign property (scroll down to see it) to AlignRight.  Resize it to about 30 pixels wide and 20 high. To the right of this, place a Line Edit, about 120 x 20, and change its name to LineEditPermA.

10. In a similar manner, place the following under these two widgets.
Text Label, text b and Line Edit, name LineEditPermB
Text Label, text a*b and Line Edit, name LineEditPermAB
Text Label, text b*a and Line Edit, name LineEditPermBA.
Change the text to I for the top two Line Edits.  For the bottom two, change ReadOnly from False to True

11. At the bottom of the group box, place a Push Button with name ButtonCalculate and text Calculate.

12. In the top center of the dialog, place a Group Box, about 150 x 150.  Change the title to Powers of a.  Fill the inside of this with a List Box, and change the name to ListBoxPowersOfA.
In a similar manner, under this, create a Group Box with title Powers of b containing a List Box with name ListBoxPowersOfB.
To the right of these, create a Group Box with title Powers of a*b containing a List Box with name ListBoxPowersOfAB
and a Group Box with title Powers of b*a containing a List Box with name ListBoxPowersOfBA.
You can do this very easily by clicking of the original Group Box to highlight it, then using Ctrl-C Ctrl-V to create a copy.  Drag the copy into position, then change the title of the Group Box and the name of the List Box.

13. Choose Edit...Slots from the Qt Designer menu, click New SLot, and add slotCalculate().  Click OK.  Press F3 to enter "connection mode."  Place the crosshair cursor over the Calculate Button, press the left mouse button, and drag to anywhere outside a group box.  CLick on the signal clicked() and the slot slotCalculate() to connect them.  This completes the development of the user interface.  CLose Qt Designer, saving the file when prompted, and press F9 to build and run the project.  It should look just right.  DO Project...Close followed by Project...OpenRecentProject to reload the project.  Now, when you click the + next to PermuteBase, you will see the names of all the widgets that you just added.  These are pointer variables that you can use in the Permute class to gain access to the widgets.

14. You will also see slotCalculate() in PermuteBase.  This is a virtual function, and you must override it in the Permute class.  Do this by right-clicking on Permute and choosing Add slot... from the menu that opens up.  Type in slotCalculate() as the declaration.  Click Apply.
You must add code to slotCalculate in Permute, not in PermuteBase!!!

15. Now right-click on Permute and choose Add member function....
The Type is QString; the Declaration is multiply(QString secondP, QString firstP).  Click Apply.
This function will calculate  the result of carrying out two successive permutations, and
you will have  to write it yourself.  But to check that everything is mechanically sound, open up permute.cpp and type in the following C++ code, which works correctly for permutations of two elements so that your function looks like this:

QString Permute::multiply(QString secondP, QString firstP){
   if (firstP == "I")
        return secondP;
   if (secondP == "I")
        return firstP;
   if (firstP == "(12)" && secondP == "(12)")
        return "I";
   return "I";
assert(false) causes an error.  It is a good statement to place before any line in your code that should never be reached if the input is correct.
Be sure that you have typed "==" (double equals - test for equality) rather than "=" (assignment).

16. Again right-click Permute and choose Add member function.  The Type is void.  The declaration is DisplayPowers(QString perm, QListBox* listBox).
This function will display the powers of  the permutation "perm" in the specified list box, stopping once it finds a power that equals the identity permutation.  Here is a version of this function
that is correct only for permutations of two elements.  You will have to write the version that is correct in general.

void Permute::displayPowers(QString perm, QListBox* listBox){
      listBox->clear();    //clear out the box
      if (perm == "I")
      else if (perm == "(12)") {
Of course, you will need to replace this with a function that calls the
function multiply() inside a while loop.

17. Now open up permute.cpp and add this code for slotCalculate, which will be called when you press the Calculate button.  This should read the permutations a nd b, multiply them in both orders, display the results, and display all the powers.  Here is a version of the function that will work,
and you may not even need to change it in your final version.

void Permute::slotCalculate(){
     LineEditPermAB->setText(multiply(LineEditPermA->text(), LineEditPermB->text()));
     LineEditPermBA->setText(multiply(LineEditPermB->text(), LineEditPermA->text()));
     displayPowers(LineEditPermA->text(), ListBoxPowersOfA);
     displayPowers(LineEditPermB->text(), ListBoxPowersOfB);
     displayPowers(LineEditPermAB->text(), ListBoxPowersOfAB);
     displayPowers(LineEditPermBA->text(), ListBoxPowersOfBA);

18. At the top of permute.cpp
#include <qlistbox.h>
#include <qlineedit.h>

19. Press F9 to build and run the project.  If you get build errors, press F4 to see them, and fix them. Once the program runs, it should work perfectly, but only for the identity partition "I" and for "(12)". Your job is to modify multiply() and displayPowers() so that it works for any permutations of {1...9}.  This will not change the user interface in the slightest.  The only aspect of this that is in any way specific to Linux is that you will be using the QString class to manipulate the strings that describe permutations.

20. To transfer your project to another computer, or to hand it in, first choose Build..DistClean from the main menu (not essential, but it saves space, so that even a large project fits on a floppy).  Then choose Tools.Ark.  Either choose File...New from the menu or click the leftmost (New) icon on the toolbar.  Navigate to the directory just above proj_permute (so that you see the folder proj_permute in the window), and type in as the file name.  (For handing in homework, you should build your own name into the file name).  Click Save.  Now choose Action...Add Directory (or click the fourth icon from the left on the toolbar).  Double-click on the directory proj_permute to move to it. You will see four subdirectories, including permute.  Click OK.  You should see all the files in the archive, but sometimes Ark will say "No files in current archive."  Don't worry-- just exit.  Choose Tools...Ark, then choose File...Open and navigate to the directory above proj_permute, and double click on  You should see a directory tree whose root is proj_permute.

21. To install the project to another computer, save on a floppy.  On the new computer, start up KDevelop and choose Tools...Ark.  Open on the floppy. Navigate to the directory above where you want proj_permute to be, and choose Action...Extract (or click the Extract icon on the toolbar).  You should then be able to open and build the project.  You can also just rebuild it in a different directory on the same computer.

22. If the project fails to build correctly on the other computer (perhaps because it has a different version of Qt or KDE), you can build an empty KDE project in a different directory and add all the source files to it.  The only files that you really need are permutebase.ui, permute.h, permute.cpp, and main.cpp.

23. To hand in your completed project, create a Zip file containing permutebase.ui, permute.h, permute.cpp, and main.cpp and email it to  Alternatively, you can email the Zip file that you created in step 20.  In either case, though, verify that you can re-create the project in a new directory on your computer, or on a different computer.

Grading guidelines:

7 points if the program works correctly as specified above.
1 point extra if you add calculation and display of the inverses of a and b.
1 point extra if you submit the project at class on Wednesday, July 3 (or before class by email)

1 point extra if you add calculate and display of b conjugated by a: a*b*a-1
1 point extra if you add error checking that reports, using the class QMessage, when the permutation a or b was not syntactically valid.  It would be nice to allow the user to put spaces in the input, so that "(1 2 3)   (45)" is treated the same as "(123)(45)", but this is not a requirement.

1 or 2 points off for minor bugs.
Up to 4 points off for major bugs (e.g. powers work, but products are wrong,
or permutations with more than one cycle come out wrong)
We will grade your executable program, not your source code.  Good
formatting, meaningful variable names, comments, and other elements of good
programming style are left to your conscience.

Experience has shown that the easiest way to implement multiply() is to use the "Pure Cycle" approach described in the notes passed out at the first class.
Use an array of bool to keep track of which elements you know the answer for.  Life is easier if you index the array with characters like '1' and '2' instead of with integers.
Write a function that takes a permutation as a QString, like (12)(357) and an input character like '1' and calculates an output character like '2'.  By calling this function twice, you can determine the effect of the product of two permutations on an symbol.
Then just trace though cycles until you have accounted for all of the elements '1' through '9'.  Remember that if the result its identity permutation, multiply() must return "I" instead of the empty string.
The QString class has all the functions that you will need.
find() will let you locate the first instance of a character like '' or ')'.
The operator [] lets you read (but not necessarily modify) an individual character.  According to the documentation, this returns a QChar, not a char, but it appears that for ASCII characters a QChar can be used in place of a char.
The operator += lets you append a string like "(46)" to an existing QString.

A lazy but effective way to find the inverse of permutation a is to calculate all the powers of a and to stop when one more multiplication by a will give the identity.

To use the debugger, click in the gray margin to the left of any line of code where you want the program to stop.  A circular breakpoint symbol appears.
Start the program with Debug...Start.  When you hit the breakpoint, you can inspect the values of variables, then continue execution using the four debug icons at the right of the main toolbar.