Declarations of functions associated with group_I.
Version of Monday 23 September 2024.

The first two functions remove the selected component from the permzbi. The size of the permzbi is decreased by one, and any components that had a higher value than the removed component are decremented by one, resulting in a correct permzbi.

The third function does the opposite, inserting a new component at the indicated location. The size of the permzbi is increased by one, and any components that have a value equal to, or greater than, the inserted component are incremented by one, resulting in a correct permzbi.

    /* I1 */ permzbi erase_by_index (int const index) const;
    /* I1 */ permzbi erase_by_value (int const value) const;
    /* I1 */ permzbi insert (int const index, int const value) const;

The next function produces a hash value suitable for use with unordered associative containers. In this implementation, each component of a permzbi is stored as an int. The bits of each int are rotated a different* distance, and the results are XORed together. Of course, there are other ways to produce a good hash function.

    /* I2 */ struct p_hash;       

* Not necessarily different if the number of components of the permzbi exceeds the number of bits in an int.

File group_I/test_I2.h has a lengthy routine to verify that p_hash delivers a well-behaved hash function.

The next functions produce a generalized out_riffle or in_riffle, where the (virtual) pack of cards need not be divided into exactly two parts, but into a larger number instead. The number of parts must be a factor of the permzbi size, and all parts will contain the same number of (virtual) cards.

    /* I3 */ permzbi out_riffle (int const packets) const;
    /* I3 */ permzbi in_riffle  (int const packets) const;

The next function generalizes riffles further, producing the out_riffle and in_riffle as special cases.

    /* I3 */ permzbi gen_riffle (permzbi const & o) const;

Functions out_riffle and in_riffle are provided to serve their special cases, because are anticipated to run faster than gen_riffle.

Many authors use the term shuffle instead of riffle for this purpose, but riffle is preferred here in group_I for two reasons:

• There are many kinds of shuffling, and riffling is only one of them. The functions here are based specifically on the riffle method of shuffling.
• The C++ Standard Library has functions with "shuffle" in their name intended to produce random shuffles. (In fact, one of them is used in permzbi::random.) However, the shuffling done here is the idealized version studied by mathematicians, which is completely non-random.

Here are two examples of how functions _riffle work. The original permutation, of fifteen components, is divided into three parts, which are then interleaved in various ways. There are three parts because the directing permutation has three components. Some dashes have been inserted to make the pattern easier to see.

Original permutation:
		( 14  4  3  2  0 —  1  8 10  6  5 — 13 11  9 12  7 )
After the 6 versions of gen_riffle, each starting with the original:
ref. no.	directing permutation	result
0	( 0 1 2 )	( 14  1 13 —  4  8 11 —  3 10  9 —  2  6 12 —  0  5  7 )
1	( 0 2 1 )	( 14 13  1 —  4 11  8 —  3  9 10 —  2 12  6 —  0  7  5 )
2	( 1 0 2 )	(  1 14 13 —  8  4 11 — 10  3  9 —  6  2 12 —  5  0  7 )
3	( 1 2 0 )	(  1 13 14 —  8 11  4 — 10  9  3 —  6 12  2 —  5  7  0 )
4	( 2 0 1 )	( 13 14  1 — 11  4  8 —  9  3 10 — 12  2  6 —  7  0  5 )
5	( 2 1 0 )	( 13  1 14 — 11  8  4 —  9 10  3 — 12  6  2 —  7  5  0 )
After out_riffle:
same as ref. 0		( 14  1 13 —  4  8 11 —  3 10  9 —  2  6 12 —  0  5  7 )
After in_riffle:
same as ref. 5		( 13  1 14 — 11  8  4 —  9 10  3 — 12  6  2 —  7  5  0 )

Similar, but now five parts:

Original permutation:
		( 14  4  3 —  2  0  1 —  8 10  6 —  5 13 11 —  9 12  7 )
After 8 of the 120 versions of gen_riffle, each starting with the original:
ref. no.	directing permutation	result
0	( 0 1 2 3 4 )	( 14  2  8  5  9 —  4  0 10 13 12 —  3  1  6 11  7 )
1	( 0 1 2 4 3 )	( 14  2  8  9  5 —  4  0 10 12 13 —  3  1  6  7 11 )
2	( 0 1 3 2 4 )	( 14  2  5  8  9 —  4  0 13 10 12 —  3  1 11  6  7 )
3	( 0 1 3 4 2 )	( 14  2  5  9  8 —  4  0 13 12 10 —  3  1 11  7  6 )
… 112 versions omitted …
116	( 4 3 1 0 2 )	(  9  5  2 14  8 — 12 13  0  4 10 —  7 11  1  3  6 )
117	( 4 3 1 2 0 )	(  9  5  2  8 14 — 12 13  0 10  4 —  7 11  1  6  3 )
118	( 4 3 2 0 1 )	(  9  5  8 14  2 — 12 13 10  4  0 —  7 11  6  3  1 )
119	( 4 3 2 1 0 )	(  9  5  8  2 14 — 12 13 10  0  4 —  7 11  6  1  3 )
After out_riffle:
same as ref. 0		( 14  2  8  5  9 —  4  0 10 13 12 —  3  1  6 11  7 )
After in_riffle:
same as ref. 119		(  9  5  8  2 14 — 12 13 10  0  4 —  7 11  6  1  3 )