JosephusCS Documentation



      This document applies to the C# Version 2.1.1.11665 of JosephusCS,
      Copyright (c) 1981-2008 by author: Harry J. Smith, Saratoga, CA.


Introduction -

When you execute the program JosephusCS.exe it responds by displaying the 
Startup form:


 


Just click the Run button and the Run form is displayed.

Run form -


 


The Run form has one large text box for text output.

If the program is executed from the DOS prompt with one or more arguments, the 
arguments are ignored.

Pressing the Help F1 key causes the Help form to be displayed:


 


The Help form is scrollable and resizable. It helps explains what the program 
does.

JosephusCS is a program that solves the Josephus Permutation problem:

  Challenge given in REC Jan/Feb/Mar 1991 on page 24.
  "The Thousand Roman Slaves" suggested by Steve Wagler

  Original Problem: 1000 slaves in a circle, numbered 1 to 1000, are all to
  be shot except one lucky survivor. The order of shooting is 1, 3, 5, etc.,
  always alternating, and always immediately removing the fallen bodies. Once
  a body has fallen, it is no longer considered part of the circle for
  purposes of future counting and alternation. Example, n=6: Shoot 1,3,5,2,6;
  4 survives.

  The General Problem: There is an ordered set of n objects arranged in a
  circle with object i (1 <= i <= n) in position i. All n objects are
  selected and removed in a certain order and placed in a new circle with
  the new position number k beings the order of selection. Object f is
  selected first. After each selection, m minus 1 of the remaining objects
  following the one removed are skipped and the next object is then
  selected. We are interested in the nature of the permutation generated by
  this process, its fixed elements, and in particular the original position
  L of the last object selected. Note that m and f can be as low as 1 and
  can be larger than n.

  n = The number of objects in the circle
  f = index of first object to be selected [1, n]
  m = difference in index of items selected, m = 2 => every other

  "Max Pointed Plotted" can be set to a value from 1 to 1000000. The
  nominal starting value is 200 and it can only be changed on the Startup
  form. Large values of this parameter can cause the Plot form to take a
  very long time before the plot appears and the program may have to be
  terminated manually by clicking the X in the upper right hand corner of
  the Plot form or the Run form. If n is greater than Max Points Plotted,
  only the first Max Points Plotted points will be plotted.

  See Knuth, The Art of Computer Programming, Vol. 1, Pages 158-159, 181,
  516, 521 and Vol. 3, Pages 18-19, 579.

--------------------------------------------------------------------------------

            +------------Function Keys on Run form------------+
            |   F1  => Display Help form                      |
            |   F2  => Quit and go back to the Startup form   |
            |   F5  => Get Status of calculation              |
            |   F6  => Display Configuration form             |
            |   F7  => Outputs a simple permutation report    |
            |   F8  => Outputs a detailed permutation report  |
            |   F9  => Toggle Logging to Log file on/off      |
            |   F11 => Clear output text box                  |
            |   F12 => Brings up the Plot form and plots      |
            |   Ctrl+F9 => Clear Log File                     |
            |   ESC => Interrupt/Abort a long calculation     |
            +-------------------------------------------------+
--------------------------------------------------------------------------------

  Example output:
--------------------
  n = 1000,  f = 1,  m = 2:  Object 976 was selected last!
  There is 1 fixed element:  1.
--------------------
  n = 1000,  f = 32767 => 767,  m = 32767:  Object 481 was selected last!
  There are 5 fixed elements:  41, 178, 619, 710, 718.
--------------------
  n = 1000,  f = 1,  m = 1:  Object 1000 was selected last!
  There are 1000 fixed elements:  1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ... .
--------------------
  Execution order, when object i was selected:
  5 4 6 1 3 8 7 2 

  Order of execution, object # selected on k'th selection:
  4 8 5 2 1 3 7 6 

  The resulting permutation expressed in cyclic notation:
  (1, 5, 3, 6, 8, 2, 4)(7)

  The fixed element in this Josephus permutation is:
  7 

  n = 8,  f = 4,  m = 4:  Object 6 was selected last!
  There is 1 fixed element:  7.
--------------------

-Harry


Function keys -

The function keys described here or used on the Run form.

F1 => Display Help form.


F2 => Quit the Run form and go back to the Startup form:

If a calculation is running, indicated by the word **Running** displayed on the 
Run form, when F2 is pressed, it is treated as an Abort Calc. request, with the 
message:

      When **Running**, select Quit twice to quit


F5 => Get Status of calculation:

Press the F5 key while a computation is being performed and a message like 

     Orbits:  Percent done, Memory in use = , DT =  sec.

will be displayed in the output text box. This is the same as the "Status of 
Calc." command button.


F6 => Display Configuration form:

Press the F6 key and the Configuration form will appear. F6 is the same as the 
"Configuration" command button.


F7 => Outputs a simple permutation report:

Press the F7 key and a simple permutation report will be output. For example:

      n = 100,  m = 2,  f = 1:  Object 72 was selected last!
      There is 1 fixed element:  1.

F7 is the same as the "Report" command button.


F8 => Outputs a detailed permutation report:

Press the F8 key and a detailed permutation report will be output. For example:

Execution order, when object i was selected:
1 51 2 76 3 52 4 99 5 53 6 77 7 54 8 89 9 55 10 78 11 56 12 95 13 57 14 79 15 58
 16 90 17 59 18 80 19 60 20 98 21 61 22 81 23 62 24 91 25 63 26 82 27 64 28 96 2
9 65 30 83 31 66 32 92 33 67 34 84 35 68 36 100 37 69 38 85 39 70 40 93 41 71 42
 86 43 72 44 97 45 73 46 87 47 74 48 94 49 75 50 88 

Order of execution, object # selected on k'th selection:
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 5
7 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 97 99 2 6 10 14 18 22
 26 30 34 38 42 46 50 54 58 62 66 70 74 78 82 86 90 94 98 4 12 20 28 36 44 52 60
 68 76 84 92 100 16 32 48 64 80 96 24 56 88 40 8 72 

The resulting permutation expressed in cyclic notation:
(1)(51, 26, 57, 29, 15, 8, 99, 50, 63, 32, 90, 73, 37, 19, 10, 53, 27, 14, 54, 6
4, 92, 87, 44, 81, 41, 21, 11, 6, 52, 82, 71, 36, 80, 93, 47, 24, 95, 48, 91, 46
, 62, 66, 67, 34, 59, 30, 58, 65, 33, 17, 9, 5, 3, 2)(76, 85, 43, 22, 56, 96, 94
, 74, 69, 35, 18, 55, 28, 79, 40, 98, 75, 38, 60, 83, 42, 61, 31, 16, 89, 45, 23
, 12, 77, 39, 20, 78, 70, 68, 84, 86, 72, 100, 88, 97, 49, 25, 13, 7, 4)

The fixed element in this Josephus permutation is:
1 

n = 100,  m = 2,  f = 1:  Object 72 was selected last!
There is 1 fixed element:  1.

F8 is the same as the "Report All" command button.


F9 => Toggle Logging to Log file on/off:

If the "Logging screen to log file mode is off it will be turned on, if on it 
will be turned off. F9 is the same as the "Logging is On/Off" command button.


F11 => Clear output text box:

This clears the output text box. F11 is the same as the "Clear Output" command 
button.


F12 => Brings up the Plot form and plots:

If the Plot form is not up, this causes the Plot form to come up and to plot the 
currently defined permutation. F12 is the same as the "Plot" command button.


Ctrl+F9 => Clear Log File:

This clears the log file and writes a header message in it.


ESC => Interrupt/Abort a long process:

The ESC key from the Run form while a calculation is running is the same as the 
"Abort Calc" command button. It can be used after the program has been asked to 
perform a task that is taking longer than the operator is willing to wait.

One of the messages:

      Manually aborted before Orbits finished
      Manually aborted before report finished

will appear. The first one appears if we were in the process of computing orbits 
of the permutation. The second appears if we were in the process of giving a 
detailed report of the permutation.


Command buttons -

There are 10 command buttons on the Run form:

      Abort Calc.: Same as ESC key.
      Status of Calc.: Same as F5 key.
      Configuration: Same as F6 key.
      Report: Same as F7 key.
      Report All: Same as F8 key.
      Plot: Same as F12 key.
      Quit: Quit the Run form and go back to the Startup form. Same as F2 key
      Clear Log File: Clears the log file, same as Ctrl+F9 key.
      Logging Is On/Off: Same as F9 key.
      Clear Output: Same as F11 key.

If the Quit button, File menu Exit, the Run form's Close button Alt+F4, or Upper 
right hand X button is selected when a calculation is running, indicated by 
**Running** being displayed on the Run form, the calculation is automatically 
aborted. The message

      When **Running**, select Quit twice to quit

is displayed in the text output text box and a second quit request is required 
to quit.

If a calculation is not running, the File menu Exit, the Run form's Close button 
Alt+F4, or Upper right hand X button will totally end the program without 
stopping at the Startup form. The Quit button or F2 will close all open forms 
and return to the Startup form with the previously selected parameters.

The Run form has a File and a Help menu button. The File menu has 
Exit. The Help menu has Help form and About...

Exit is the same as the Quit button except it does a complete exit.

Help form is the same as the F1 key and causes the Help form to be displayed.
About will bring up a dialog box with Application Title, Version, Application 
Description and a URL to obtain the latest version of the program:


 


Click the OK button, press Enter, or hit the escape button to remove this box.


Click the Plot button and the Plot form is displayed and the currently selected 
permutation is plotted.


Plot form -


 


This is an example of the plot form plotting the case of n = 100, f = 1, and m = 
2.

Object n is plotted at the very top of the circle. Object 1 is the next point to 
the right clockwise.

The red lines are drawn from each item in the original circle to where it ends 
up in the new circle. The extra part of the line outside of the circle shows 
that it is a point on the new circle. Some plots may have a small extra part of 
the line outside of the circle that should be ignored.

If n is greater than Max Points Plotted (selectable on the Startup Frame), only 
the first Max Points Plotted points will be plotted.

The "Number n", "First f", and "Skip m" all work the same. To change one of 
these, edit its value in the TextBox and press Enter or click the "Change It" 
button. If the edited value is unacceptable, the "Change It" button will be 
disabled and the value will not change. If you clear the TextBox and try to 
accept it, the current value will be displayed in the TextBox.

If you click the "-1" button under the "Change It" button and the current value 
is greater than 1, the current value will be reduced by one, the value in the 
TextBox will be updated and a new plot will be generated.

If you click the "+1" button under the "Change It" button and the current value 
is less than Max Number n, the current value will be increased by one, the value 
in the TextBox will be updated and a new plot will be generated.

If you click the "Plot" button, a new plot will be generated with the current 
values of n, f, and m.

The "About" button, will bring up a dialog box with Application Title, Version, 
Application Description and a URL to obtain the latest version of the program.

The "Exit" button will terminate the current plot calculation if any, close the 
Plot form and go to the Run form.


Messages and error reports -

There are several different messages and/or error reports that are a result of 
user action (or conceivably an error in the JosephusCS program):

JosephusCS - The Flavius Josephus Permutation Program, C# Version 2.1.xxxx.xxxxx
Run on:  by 

Output Screen: Cleared mm/dd/yyyy hh:mm:ss am/pm

Orbits:  Percent done, Memory in use = , DT =  sec.

Manually aborted before Orbits finished

Manually aborted before report finished

When **Running**, select Quit twice to quit

Log file  Opened for Append mm/dd/yyyy hh:mm:ss am/pm
Full name = \

Log file  Closed mm/dd/yyyy hh:mm:ss am/pm

File  opened for writing
Full name = \
Writing file 
Log file  Cleared mm/dd/yyyy hh:mm:ss am/pm
Full name = \

File JosephusCSHelp.txt opened for reading
Full name = \JosephusCSHelp.txt

Cannot open file JosephusCSHelp.txt for input
Not in current directory 
OpenRead: Could not find file \JosephusCSHelp.txt'.

Cannot open  for output
Full name = \
OpenAppend: Access to the path '\' is denied.
Aborting file write...

Cannot open  for output
Full name = \
OpenWrite: Access to the path '\' is denied.
I/O operation aborted by operator!
Aborting file write...


Other forms -

Other forms that can be displayed to help in using the program are the Startup, 
Help, Configuration, Change File Path/Browse For Folder, Select a File, and Plot 
forms. On all forms except the Run form, pressing the ESC key will remove the 
form.


Startup form -

The Startup form is shown above and has five parameters that can be set before 
the program runs:

"Max Number n <= 1000000" can be set to a value from 1 to 1000000 and it can 
only be changed on this Startup form. The nominal starting value is 1000. Number 
n cannot be set larger than this.

"Number n" can be set to a value from 1 to Max Number n. The nominal starting 
value is 100 and it can be changed on the Plot form. n = The number of objects 
in the circle.

"First f" can be set to a value from 1 to 1000000. The nominal starting value 
is 1 and it can be changed on the Plot form. f = index of first object to be 
selected [1, n].

"Skip m" can be set to a value from 1 to 1000000. The nominal starting value is 
2 and it can be changed on the Plot form. m = difference in index of items 
selected, m = 2 => every other item.

"Max Pointed Plotted" can be set to a value from 1 to 1000000. The nominal 
starting value is 200 and it can only be changed on this Startup form. Large 
values of this parameter can cause the Plot form to take a very long time before 
the plot appears and the program may have to be terminated manually by clicking 
the X in the upper right hand corner of the Plot form or the Run form. If n is 
greater than Max Points Plotted, only the first Max Points Plotted points will 
be plotted.

These five values are tested as they are edited. Zeros on the left or spaces on 
the left or right are removed so you will not see them. These numbers are 
displayed in bold face font iff they are acceptable values. If any of the five 
values are unacceptable, the Run button is disabled.

A "Default Settings" button is provided to reset the five parameters to their 
original values.

The Run button is used to bring up the Run form. It can be used after a Run form 
exits to reinitialize JosephusCS and start running again. The Exit button will 
terminate the program.


Help form -

The Help form was shown and partially described above. It has a File menu button 
that has a menu with Print Setup, Print..., Print Preview and Exit. The Print 
Setup will bring up the Windows printer setup dialog box so you can select the 
printer to use. The Print... will start the printing process to start printing 
the help file. This will normally bring up the printers dialog box. The Print 
Preview does just that, it can also be used for printing. The Exit does the same 
thing as pressing the escape key; the Help form is removed.

This form also has a "F3 Find:" button, a "F2 Up" button and a small text box 
for entering a string of characters to find. Pressing F3 is the same as clicking 
the "F3 Find:" button, the text in the small text box is searched for. Pressing 
F2 is the same as clicking the "F2 Up" button, same as F3 except the search is 
done from the current location towards the top of the large text box.

If during a find the text is not found, the sound from NotFound.wav is heard. If 
it is found, but only by starting over from the other end of the text, the sound 
from Wrap.wav is heard. This sound process uses the system file winmm.dll. If 
that file cannot be found, there will be no sound.

A short beep is also heard when the text is found. The beep is 277Hz = middle C# 
for a normal search and 554Hz one octave above for a search up. The beep process 
uses the system file kernel32.dll. If that file cannot be found, there will be 
no beep.

Text can be copied from the large text box to the small text box by selecting 
the text with the left mouse button and pressing Ctrl-F.

The Help form is unique in that more than one copy can be brought up at the same 
time. This may or not be useful, but it illustrates a technique in Windows 
programming.


Configuration form -

The Configuration form is displayed when function key F6 is pressed or the 
"Configuration" command button is selected on the Run form:


 


This form allows you to change:

      Log to file mode.
      Name of Log file.

It also shows the Home Directory, File path, and the name of the log file if Log 
to file mode is on. The Browse For Folder form can be brought up by selecting 
the "Change File Path" command button, and the Select a file form can be brought 
up by selecting "Select a File" command button.

Clicking the "Change It" button when its text box is empty will bring up the 
current value. It can be edited, and a second click with the text box not empty 
will accept the entry. A space at the right or a Return/Enter key will also 
accept it.

The Log to file mode can be changed/toggled by clinking the corresponding 
button. If the mode is on, the button will says "Is On", then clicking it will 
turn the mode off and the button will change to "Is Off". If the mode is off, 
the button will says "Is Off", then clicking it will turn the mode on and the 
button will change to "Is On".

The Log to file mode and name of Log file interact in that if the file name is 
changed while a log file is open, the file name of the open file will not change 
until the log file is closed and reopened.


Browse For Folder form -

The Browse For Folder form is displayed when the "Change File Path" command 
button is selected on the Configuration form:


 


To change the current directory to be used for the Log file, use this form to 
select a path. This form is resizable as is the Run, Help, and Select a file 
forms.


Select a File form -

The Select a file form is displayed when the "Select a File" command button is 
selected on the Configuration form:


 


This provides a way to browse and select a file. If a file is selected, it can 
then be used to set a file name on the Configuration form by clicking the file 
name "Change It" buttons. The first click enters the file name in the text box 
and a second click will accept it. This form can also be used to change the file 
path.

The list box in the lower right hand corner of the Configuration form is a list 
of the files in the currently selected file path. The wild card selection for 
these files (*.log, or *.*) is the same as last used on the Select a file form.


How things are computed -

int[] a;  // Working array of objects
          // Ends up with a[i] = when object i was selected
int[] b;  // Record of objects selected
          // Ends up with b[i] = object # selected on k'th selection
int c;    // Index to current object being scanned
int f;    // # of first object to be selected
int i;    // Utility index
int k;    // Number of objects selected (killed) so far
int m;    // m for selecting every m'th object
int n;    // The total number of objects in the circle to start with
int p;    // Index to previous object
int r;    // Remaining number of objects in the circle
int s;    // Number of fixed (stationary) elements in permutation
int maxS; // Up to maxS saved fixed elements (maxS = 10)
int[] x;  // Saved fixed elements

void Orbits() // Determine the orbits
// uses n, f, and m as input
// computes a[], b[], and s
{
    for (i = 1; i < n; i++)
        a[i] = i+1;                 // Set position i to point to next position
    a[n] = 1;
    p = 1 + ((f % n) + n - 2) % n;  // Init previous position based on f
    k = 1;  r = n;
    do
    {
        if ((1 < k) && (k < n))     // If not first or last selection
        {
            for (i = 1; i <= (m - 1) % r; i++)  // Move m-1 positions (zero OK)
                p = a[p];
        }
        c = a[p];                   // Update current position
        b[k] = c; c = a[c];         // Select the object at c
        a[a[p]] = k;                // Save execution order
        k++; r--;
        a[p] = c;                   // Re-link circular chain of pointers
    } while (k <= n);               // Until all are selected
    a[c] = n;                       // a[c] was clobbered, so restore it
    s = 0;                          // Count number of fixed elements
    for (i = 1; i <= n; i++)
        if (b[i] == i)
            s++;
} // Orbits

void ReportDetails()  // Generate detailed output
// uses n, a[], and b[] as input
{
    WriteLn("Execution order, when object i was selected:");
    for (i = 1; i <= n; i++)
        Write(a[i] + " ");
    WriteLn();  WriteLn();
    WriteLn("Order of execution, object # selected on k'th selection:");
    for (i = 1; i <= n; i++)
        Write(b[i] + " ");
    WriteLn();  WriteLn();
    WriteLn("The resulting permutation expressed in cyclic notation:");
    p = b[1];  c = 1;
    int[] t = new int[n + 1];   // temporary working array of objects
    for (i = 1; i <= n; i++) t[i] = a[i];
    do
    {
        Write("(");
        do
        {
            if (c != 0)
            {
                Write("" + c);
                t[p] = 0; p = c;
            }
            c = t[p];
            if (c != 0) Write(", ");
        } while (c != 0);
        Write(")");
        i = 0;
        do
        {
            i++;  c = t[i];
        }
        while ((c == 0) && (i != n));
        if (c != 0) p = b[c];
    } while (c != 0);
    WriteLn();  WriteLn();
    ReportFixed();
} // ReportDetails

void ReportFixed() // Generate output of all fixed elements
// uses n, s, and b[] as input
{
    string Ss;                      // String "s" or "" if s = 1
    string Sis;                     // String "are" or "is" if s = 1 }
    if (s == 1)                     // Setup is or are
    {
        Ss = ""; Sis = "is";
    }
    else
    {
        Ss = "s"; Sis = "are";
    }
    Common.WriteLn("The fixed element" + Ss + " in this Josephus permutation " + 
Sis + ":");
    for (i = 1; i <= n; i++)
    {
        if (b[i] == i)                  // Output fixed elements
            Common.Write(i + " ");
    }
    if (s == 0) Common.Write("None!");
    Common.WriteLn();
    Common.WriteLn();
} // ReportFixed

void ReportResults() // Generate normal output
// uses n, f, m, s, maxS, b[], and x[] as input
{
    GenerateFixed();
    int nx = 0;                     // Number of saves fixed elements
    string Ss;                      // String "s" or "" if s = 1
    string Sis;                     // String "are" or "is" if s = 1 }
    if (s == 1)                     // Setup is or are
    {
        Ss = ""; Sis = "is";
    }
    else
    {
        Ss = "s"; Sis = "are";
    }
    Common.Write("n = " + n + ",  m = " + m + ",  f = " + f);
    if (f > n) Common.Write(" => " + 1 + (f - 1) % n);
    Common.WriteLn(":  Object " + b[n] + " was selected last!");
    Common.Write("There " + Sis + " " + s + " fixed element" + Ss);
    if (s > 0)
    {
        nx = s;
        if (nx > maxS) nx = maxS;
        Common.Write(":  ");
        for (i = 1; i <= nx; i++)
        {
            Common.Write("" + x[i]);
            if (i != nx) Common.Write(", ");
        }
    }
    if (s > nx) Common.Write(", ... ");
    Common.WriteLn(".");  Common.WriteLn();
} // ReportResults

GenerateFixed() // Generate array of first fixed elements
// uses n, maxS, and b[] as input
// computes x[]
{
    Int sl = 0;                // number of fixed elements found
    for (i = 1; i <= n; i++)
    {
        if (b[i] == i)
        {
            sl++;
            if (sl <= maxS)
                x[sl] = i;     // Save up to maxS fixed elements
            else
                return;
        }
    }
} // GenerateFixed


Distribution files -

The distribution files can be downloaded from my website:

      http://www.oocities.com/hjsmithh/

in the Files to Download section

      http://www.oocities.com/hjsmithh/download.html#Joseph .

When you install the program using the distribution file JosephusCS21?.exe or 
JosephusCS21?.zip, a folder is created with 3 subfolders:

      +--JosephusCS 2.1
        +--doc
        +--run
        +--src

The main folder has two files sseexec.dat and SSEun.dat. These are needed to be 
able to uninstall the program

The doc subfolder has the following 4 files:

      00.txt         (A short list of features)
      Fixes.txt      (A list of features and fixes added to each version)
      JosephusCS.doc (Microsoft Word file)
      JosephusCS.txt (Plain ASCII text copy of the .doc file without graphics)

There is also available on my website a copy of the .doc file in an Adobe 
Acrobat Reader file JosephusCS.pdf.

http://www.oocities.com/hjsmithh/Josephus/index.html .

The run subfolder has the following 7 files

      00.txt
      JosephusCS.exe
      JosephusCS.log
      JosephusCSHelp.txt
      Log.log
      NotFound.wav
      Wrap.wav

The .exe file is executed from there.

The src subfolder has all the source files needed for development:

      00Note.txt
      AboutForm.cs
      AboutForm.resx
      AssemblyInfo.cs
      Common.cs
      ConfigEdit.ico
      ConfigForm.cs
      ConfigForm.resx
      COPYING.txt
      cs.ico
      Global.cs
      harry.jpg
      HelpForm.cs
      HelpForm.resx
      JosephusCS.cs
      JosephusCS.csproj
      JosephusCS.ico
      JosephusCS.sln
      JosephusCS.suo
      JosephusCS.csproj.user
      PlotControl.cs
      PlotControl.resx
      PlotForm.cs
      PlotForm.resx
      RunForm.cs
      RunForm.resx
      StartupForm.cs
      StartupForm.resx


The end -

Report any errors by sending me a letter, an e-mail or call me at my home phone.




-Harry

Harry J. Smith
19628 Via Monte Dr.
Saratoga, CA 95070-4522, USA

Home Phone:  1 408 741-0406
E-mail:  hjsmithh@sbcglobal.net
Website:  http://www.oocities.com/hjsmithh/

Return to Josephus Permutation Problems
Return to Harry's Home Page


This page accessed times since July 8, 2008.
Page created by: hjsmithh@sbcglobal.net
Changes last made on Wednesday, 09-Jul-08 09:31:32 PDT

1