List Commands Library for 50g

[DavidM]

Here's a couple illustrative examples of how the masks I described above are used. I'm representing the masks in these examples as a string of numbers separated by spaces for clarity.

Combination Masks

Example: a list of 5 items, we want all combinations of 3

Lexicographic stepping for DOCOMB/DOPERM combinations starts with the highest order form and works its way down to the lowest. So the first mask is created with a series of 1s that matches the count of selected elements, followed by 0s for the remainder:

1 1 1 0 0

The mask is then stepped down lexicographically in each iteration of the loop until the lowest order form is found:

1 1 1 0 0
1 1 0 1 0
1 1 0 0 1
...
0 1 1 0 1
0 1 0 1 1
0 0 1 1 1

The mask for each iteration is applied to the source list such that the resulting selection contains only the elements that correspond to the 1s. So if our source list is:

{ A B C D E }

...then the resulting combinations that correspond to the iterative masks are:

Code:

Src List/Mask  Resulting Sublist
-------------  -----------------
A B C D E   
1 1 1 0 0      A B C    
1 1 0 1 0      A B   D  
1 1 0 0 1      A B     E 
1 0 1 1 0      A   C D 
1 0 1 0 1      A   C   E 
1 0 0 1 1      A     D E 
0 1 1 1 0        B C D 
0 1 1 0 1        B C   E 
0 1 0 1 1        B   D E 
0 0 1 1 1          C D E

Permutation Masks

Example: a list of 4 items

The first mask is generated with each index matching its zero-based starting position, and is thus already in the lowest-order form:

0 1 2 3

The mask is then stepped lexicographically upward until the highest order permutation is encountered:

0 1 2 3
0 1 3 2
0 2 1 3
...
3 1 2 0
3 2 0 1
3 2 1 0

The mask is applied to the source list in a similar fashion to the above description for combinations, but instead of a binary disposition (include/exclude), the mask designates the final positions of each of the source elements in the new list. So if our source list is:

{ A B C D }

...then the resulting permutation lists that correspond to the designated masks are as follows:

Code:

Src List/Mask  Resulting Permutation
-------------  ---------------------
A B C D
0 1 2 3        A B C D 
0 1 3 2        A B D C 
0 2 1 3        A C B D 
0 2 3 1        A C D B 
0 3 1 2        A D B C 
0 3 2 1        A D C B 
1 0 2 3        B A C D 
1 0 3 2        B A D C 
1 2 0 3        B C A D 
1 2 3 0        B C D A 
1 3 0 2        B D A C 
1 3 2 0        B D C A 
2 0 1 3        C A B D 
2 0 3 1        C A D B 
2 1 0 3        C B A D 
2 1 3 0        C B D A 
2 3 0 1        C D A B 
2 3 1 0        C D B A 
3 0 1 2        D A B C 
3 0 2 1        D A C B 
3 1 0 2        D B A C 
3 1 2 0        D B C A 
3 2 0 1        D C A B 
3 2 1 0        D C B A

Stepping algorithm

The heart of all of this is a subroutine I called "NextMask", which takes a mask and a boolean indicating up/down stepping and returns the next mask and a boolean indicating if the new mask is at the high/low extreme. The algorithm is a modified form of this one, with the modifications allowing for up or down stepping. No changes were needed to accommodate combinations and permutations; the exact same algorithm inherently works for both so long as they are formatted as described above.

Hope this helps!