Author's note: The C++ program discussed below, and this descriptive web site, have grown far beyond what I expected:

• Development of the program is now virtually complete, with only minor changes anticipated.
• Although this web site has been "framed out", the details of the descriptions vary from non-existent to rudimentary to polished. Work continues, but there's no telling when everything will be done.
• Creating this documentation has influenced the structure of the code in many ways: if this explanation of the code cannot be clearly organized, then the code itself is not clearly organized.

This page is a revisiting of some of the material in the same author's earlier report. That report provides code in the C++ programming language for manipulating permutations. After a few years of thought, the author decided to take another look at it, and substantial changes ensued: a few deletions, many additions.

Everyone is welcome to download this new source code, modify it, run it, and redistribute it. No copyright is claimed.

The theory of symmetric groups contains much background information pertaining to permutations. Meanwhile, the theory of alternating groups deals with half of all permutations, but is not addressed here.

In the code and in this report, a permutation is written between braces, for example {4, 0, 2, 3, 1, 6, 5}. Sometimes commas are omitted. Although braces are often used to denote a set, that concept is hardly used here, so there should be no confusion.

The earlier report provided code for each of std::vector and std::array with each of zero-based and one-based numbering, yielding four versions total. However, it might be regarded as cumbersome because of all the variations and conversions. Hence this newer treatment is limited to std::vectors with zero-based numbering.

Rationale for using std::vector instead of std::array:

• std::array does involve simpler memory management than std::vector, with the potential to run faster. However, std::array requires that the size of a permutation be known at compile time, although that value can be parameterized, and can indeed be calculated with a variety of compile-time operations.
• std::vector by contrast allows the size of a permutation to be determined at run time, giving the programmer and user greater flexibility. Also, std::vector, being the most popular container in the C++ Standard Library, has received decades of research into its efficient implementation. Hence it was chosen for the code presented in this report. A tradeoff is that std::vector normally requires dynamic memory allocation, which can be slow. However, some environments provide a small_vector optimization to eliminate this need.
• Another matter is that std::vector conveniently supports the jagged array, such as std::vector<std::vector<int>>, where the component vectors are of different length. This method is called the Iliffe vector. The need for this arises several places, for example in giving a report of the cycles of a permutation. By contrast, jaggedness would be cumbersome to simulate with something like std::array<std::array<int,10>,15>, because all the component arrays must be of the same length, in this example 10. As a result, there would be some unused components, whose existence is an invitation to error.

Also, this report opts to use permutations that are zero-based rather than one-based. Rationale:

• In C++, std::vectors, std::arrays, C-style arrays, and other sequential containers begin the indexing of their components at number zero, rather than one. Therefore, a permutation is here represented with the smallest nonnegative integers available, for instance {5, 2, 0, 1, 4, 3}. Note that a value in one permutation is often used to index a component in another permutation, and uniformity greatly simplifies everything. To employ one-based values and zero-based indices together would require error-prone conversion processes.
• Acknowledged is that this decision contrasts with the usual practice of mathematicians, who prefer the smallest positive integers for the permutations, for instance {6, 3, 1, 2, 5, 4}. The computer language Fortran, which is widely used by mathematicians, defaults to one-based numbering for arrays.

The main class here is named permzbi, formed from "permutations of zero-based integers". All code is located in namespace permzbi_lib, scattered across a number of files. No doubt, some observers will complain that there are too many files containing too many functions; any user may delete anything they dislike, and reorganize whatever is left.

There is close to a one-to-one correspondence between files named permzbi... and files named test..., for example permzbi_D2.h and test_D2.h. The test... files test and demonstrate much of what the contents of permzbi_lib can do, but they are not necessary for production, and may be deleted.

The code has been written to be reasonably straightforward and reasonably efficient. Any "fine tuning" to increase speed or reduce memory should be done by the user, who will know what their priorities are, and what their implementation offers. Modern compilers can often do wonders optimizing simple code.

The fundamental operations performed on permutations are composition and inversion. They are discussed in detail on a separate page.

Here is an introduction to the C++ code, which is in the form of a free-standing program. File main.cpp begins with brief summary, as below. Class permzbi is required, while the others are used only if needed.

namespace permzbi_lib {
    // utility     // declared in file A1
                   // defined in group_B

    class permzbi; // declared in file A2  
                   // members defined in group_C, _D, _E, _F, _G, _H, _I 
                   // non-members defined in group_Q, _R, _S
                            
    class rothe;   // declared in file A3     // to produce Lehmer codes
                   // defined in group_U

    class cycles;  // declared in file A4     // to find cycles within permzbis 
                   // defined in group_V
    
    class SJT;     // declared in file A5     // to produce permzbis according to the
                   // defined in group_W      // Steinhaus–Johnson–Trotter sequence

    class rob_sch; // declared in file A6     // to produce Young tableaux according to
                   // defined in group_X      // the Robinson–Schensted correspondence

    // group_Z is miscellaneous code to support the web page you are now reading

    // some group letters were skipped to allow room for expansion

    constexpr bool permzbi_lib_safe {true};
}

permzbi_lib_safe, when true, introduces run-time checks. It is used at many locations throughout the code. Although the run-time checks do introduce overhead, the test itself:

    if (permzbi_lib_safe) {
        // true code
    } else {
        // false code
    }

should not, because it depends on a compile-time constant that, except in debugging modes, will be optimized away by the compiler, along with the unexecutable branch of the test. Because of its distinctive name, permzbi_lib_safe is easy to find with a text editor, so that a programmer can customize what sections of code are, and are not, checked.

Utility declarations associated with file group_A/permzbi_A1.h are found in group_B.

Here are some declarations copied from the beginning of the lengthy file group_A/permzbi_A2.h. They all pertain to class permzbi:

    // private:
        SVI p_guts; // = std::vector<int> // the only data
    public:
        permzbi () = default;
        permzbi (permzbi const &) = default;
        permzbi (permzbi &&) = default;
        permzbi & operator= (permzbi const &) = default;
        permzbi & operator= (permzbi &&) = default;
        ~permzbi () = default;

The only data of class permzbi is stored in the familiar and well-supported Standard Library container SVI = std::vector<int>. A permzbi is merely an SVI that is guaranteed to always be a permutation on a zero-based set of consecutive nonnegative integers. In fact, maintenance of this invariant comprises a substantial part of the code. By contrast, a plain SVI might contain any arbitrary integers.

Remaining declarations for class permzbi appear on the following separate pages:

• Class members:
  • group_C — various operations
  • group_D — various operations
  • group_E — reverse; swap; rotate; scramble
  • group_F — previous and next permutation
  • group_G — find patterns in permutations
  • group_H — find patterns in rotated permutations
  • group_I — erase and insert; hash; riffle
• Pertinent non-members:
  • group_Q — swap counts; difference measures
  • group_R — derangements; con- and dis-junctions
  • group_S — stream support

An aim is to distribute permzbi's function definitions into #included files none of which is inconveniently large. Still, the whole body of code is a single compilation unit.

group_U provides support for Rothe charts and Lehmer codes.

group_V provides support for cycles.

group_W provides support for the Steinhaus-Johnson-Trotter sequence of permutations.

group_X provides support for the Robinson-Schensted correspondence and Young tableaux.

A discussion of operator overloading as used in permzbi.