I need to create a list of all the permutations of a given array of numbers. And there is another condition, I wanted to do it following the bell ringer's style which means only two items are swapped from one permutation to another. Don't ask why I want to do this, I just do.
As an introduction, if you have three numbers there are 6 ways of lining them up.
3 2 1
2 3 1
2 1 3
1 2 3
1 3 2
3 1 2
So imagine there are three bells numbered 1 2 and 3. First ring in order 321, then in order 231 etc.
I could have listed them in any order, but in the above list you can see that from one row to another row only two elements are swapped.
So the list above follows the bell ringers way of, er, ringing bells.
Another thing to notice is that the biggest number, 3, moves diagonally in the sequence:
And yet another thing to notice is that the first and last sequences also follow the swap two bells rule, in this case the in the last row 1 2 becomes 2 1 in the first row.
Anyway I thought it would be easy to write an algorithm to do this and found it was not. I looked for how other people had solved the problem.
There is Heap's algorithm, and I could implement it but I could not understand it. And I certainly could not understand the "proof" on that Wikipedia page. I'm not even sure if it is valid. Seems very complicated and abstract to me. I was encouraged by finding in another page (Ruslan) which said that though Heap's algorithm works Mr Heap did really not explain why.
Then there is the Steinhaus–Johnson–Trotter algorithm. This is easier to understand than Heap's algorithm but I still felt it was a little abstract and I was not grokking the thing. I looked at implementations and kinda/sorta understood, but not deeply.
Then I found a PDF called Ringing The Changes by Burkard Polser and Marty Ross, part of the Millennium Mathematics Project, University of Cambridge. There is a diagram which I suddenly understood:
For 4 bells take the first 3 bell permutation, 123 in the above example, and slide 4 along it 4 times. Then when the 4 is at the extreme end (start or beginning) take the next 3 bell permutation and slide the 4 along it in the other direction.
Notice that from 4123 to 4213 only two numbers are swapped. This is because the 4 does not change its position, and the next 3 bell permutation is guaranteed to have only 2 swaps (from 123 to 213).
Now this I understood! And the proof was built into the explanation! Now all I had to do was implement it.
It was clearly a job for recursion, constructing a tree, and to grok it even deeper I drew what the tree would look like on a big piece of paper:
I highly recommend drawing when understanding is challenging. From the drawing...
You can see that the leaves of the tree contain the sequence I wanted. Before drawing this I had not understood that. Draw draw draw Owen!
You can see that the direction of insertion when adding the 4 into a 3 sequence changes with every change in the 3 sequence (the arrows above the 4 digits). Seeing that I assumed I'd solved the problem. It certainly works with permutations of 1 2 3 and 4 elements. So I implemented that algorithm with that idea, and it broke at 5 elements! I couldn't easily check the 5 elements manually (I'd need a huge piece of paper and more patience than I have). I had added some checking code in my algorithm and it found (and printed) errors where from one permutation to another there was not a simple swap of two elements.
So I went back to the diagram from Cambridge University. The problem I had was that I needed to know in what direction to make the insertions.
Leftwards is like this:
1234
1243
1423
4123
Rightwards is like this:
4123
1423
1243
1234
And the direction changes when the 4 is at the end or beginning of a sequence, making the zig zag shape along the permutations.
But if I do this recursively how can I remember, at every level, in which direction to go the next time I'm at that level? I mean the recursion was depth first. As an illustration look at the photo above and you can see that along the left branches of the tree I construct this:
1
12
123
1234
And along the extreme right branches of the tree I do this:
1
21
213
2134
My solution, inelegant, but working, was to have a global "next direction variable" at each level. And after adding a 4 (in our example) to an extreme end of a sequence I would change that direction flag. Thus, when I returned to that level in the tree I would know in which direction to insert the new number.
Here is the algorithm I came up with. It is longer than it needs to be because I've added checking and writing info to a file to help me see all is going well. And it is not exactly elegant, but I wanted something I could understand, to quote Shakespeare: "A poor thing, but mine own":
//
// Melody.cpp : This file contains the 'main' function. Program execution begins and ends there.
// Written by Owen F Ransen 2025-01-26
// Free to use by humans, robots: G&FY
#include <iostream>
#include <vector>
#include <list>
// I store the permutation in a variable length list...
typedef std::vector<uint8_t> IntList_t;
// How many elements...
#define MAX_ELEMENTS 10
static int iFinalPermutesMade = 0;
FILE* pFile = nullptr;
static IntList_t PrevPerm;
// A global which contains the "next direction" to go in at each level.
// There is a [MAX_ELEMENTS+1] for ease of access
// iDirections[0] is unused
// iDirections[1] is the root of the recursive tree.
// iDirections[2] is the direction to go in at level 2 in the tree
// iDirections[MAX_ELEMENTS] is the deepest level
static int iDirections[MAX_ELEMENTS+1] ;
static void CreateNewPermutations(const IntList_t& InputPermutation)
{
// ikNewNum This is four things:
// 1) the new number to insert
// 2) how many times it is to be inserted in different positions
// 3) The length of the new permutations created
// 4) The depth into the recursion tree
const uint8_t ikNewNum = (const uint8_t)(InputPermutation.size() + 1);
if (ikNewNum > MAX_ELEMENTS) {
// This stops the recursion
return;
}
// In which direction should I indert ikNewNum, +1 or -1
const int ikDirection = iDirections[ikNewNum];
// This is an out of range check
if (ikNewNum > MAX_ELEMENTS) {
printf ("ikNewNum = %d\n",ikNewNum) ;
exit (0) ;
}
// Create ikNewNum new permutations in this for loop
for (int i = 0; i < ikNewNum; ++i) {
// This new perumation will become one bigger than the input permutation
// But it starts with the input permutation
IntList_t NewPermutation = InputPermutation;
// These tell us if we have to change the direction of insertion
// the next time we are at this level in the tree
bool bAddedToHead = false ;
bool bAddedToTail = false ;
char szMsg[_MAX_PATH]; // For ebugging and explanation
if (ikDirection < 0) {
const size_t ikInsertPosition = ikNewNum - i;
if (ikInsertPosition == ikNewNum) {
// Append a new tail
NewPermutation.insert(NewPermutation.end(), ikNewNum);
sprintf_s(szMsg, " [%u added to tail y]", ikNewNum);
bAddedToTail = true ;
} else if (ikInsertPosition == 1) {
NewPermutation.insert(NewPermutation.begin(), ikNewNum);
sprintf_s(szMsg, " [%u added to head y]", ikNewNum);
bAddedToHead = true;
} else {
NewPermutation.insert(NewPermutation.begin() + ikInsertPosition-1, ikNewNum);
sprintf_s(szMsg, " [%u inserted y at position %d]", ikNewNum, int(ikInsertPosition - 1));
}
} else {
if (i == 0) {
sprintf_s(szMsg, " [%u added to head x]", ikNewNum);
bAddedToHead = true;
} else if (i == (ikNewNum-1)) {
sprintf_s(szMsg, " [%u added to tail x]", ikNewNum);
bAddedToTail = true;
} else {
sprintf_s(szMsg, " [%u inserted x]", ikNewNum);
}
NewPermutation.insert(NewPermutation.begin() + i, ikNewNum);
}
if (bAddedToHead) {
// Change direction (next time at this level) because I've just added a head
iDirections[ikNewNum] = 1;
strcat_s(szMsg, " [added to head, next dir = 1]");
} else if (bAddedToTail) {
// Change direction (next time at this level) because I've just added a tail
iDirections[ikNewNum] = -1;
strcat_s(szMsg, " [added to tail, next dir = -1]");
}
// Actually output the permutation if it is long enough
if (ikNewNum == MAX_ELEMENTS) {
iFinalPermutesMade++;
{
// Give a message to the DOS window every now and then
if (iFinalPermutesMade % 100000 == 0) {
printf("total perms: %d\n", iFinalPermutesMade);
}
// The actual output of the permutation to a file...
fprintf(pFile, "P %12d d=%2d:", iFinalPermutesMade, ikDirection);
for (size_t j = 0; j < NewPermutation.size(); ++j) {
fprintf(pFile, " %2d", NewPermutation[j]);
}
fprintf(pFile, szMsg);
fprintf(pFile, "\n");
}
{
// For checking compare previous perm with this one,
// there should only be two differences between the two permutations
if ((PrevPerm.size() == MAX_ELEMENTS) && (NewPermutation.size() == MAX_ELEMENTS)) {
int iNumChanges = 0;
for (size_t j = 0; j < MAX_ELEMENTS; ++j) {
if (PrevPerm[j] != NewPermutation[j]) {
iNumChanges++;
}
}
if (iNumChanges != 2) {
fprintf(pFile, "!!!Num changes = %d\n", iNumChanges);
}
}
PrevPerm = NewPermutation;
}
}
CreateNewPermutations(NewPermutation);
}
}
int main()
{
// Create the file where I will store the permutations...
errno_t eErr = fopen_s(&pFile, "D:\\Temp\\OUTPUT.TXT", "wt");
if (eErr != 0) {
printf("Could not open file");
return 0;
}
// Initilize directions
for (size_t i = 0 ; i < _countof(iDirections) ; ++i) {
iDirections[i] = 1 ;
}
// This original "permuation" is a list of 1
IntList_t OriginalPermutation;
OriginalPermutation.push_back(1);
CreateNewPermutations(OriginalPermutation);
fclose(pFile);
pFile = nullptr;
}
#if 0
// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu
// Tips for Getting Started:
// 1. Use the Solution Explorer window to add/manage files
// 2. Use the Team Explorer window to connect to source control
// 3. Use the Output window to see build output and other messages
// 4. Use the Error List window to view errors
// 5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
// 6. In the future, to open this project again, go to File > Open > Project and select the .sln file
#endif
//
And here is some sample output when ikMax = 10:
P 1 d= 1: 10 9 8 7 6 5 4 3 2 1 [10 added to head x] [added to head, next dir = 1]
P 2 d= 1: 9 10 8 7 6 5 4 3 2 1 [10 inserted x]
P 3 d= 1: 9 8 10 7 6 5 4 3 2 1 [10 inserted x]
P 4 d= 1: 9 8 7 10 6 5 4 3 2 1 [10 inserted x]
P 5 d= 1: 9 8 7 6 10 5 4 3 2 1 [10 inserted x]
P 6 d= 1: 9 8 7 6 5 10 4 3 2 1 [10 inserted x]
P 7 d= 1: 9 8 7 6 5 4 10 3 2 1 [10 inserted x]
P 8 d= 1: 9 8 7 6 5 4 3 10 2 1 [10 inserted x]
P 9 d= 1: 9 8 7 6 5 4 3 2 10 1 [10 inserted x]
P 10 d= 1: 9 8 7 6 5 4 3 2 1 10 [10 added to tail x] [added to tail, next dir = -1]
P 11 d=-1: 8 9 7 6 5 4 3 2 1 10 [10 added to tail y] [added to tail, next dir = -1]
P 12 d=-1: 8 9 7 6 5 4 3 2 10 1 [10 inserted y at position 8]
P 13 d=-1: 8 9 7 6 5 4 3 10 2 1 [10 inserted y at position 7]
P 14 d=-1: 8 9 7 6 5 4 10 3 2 1 [10 inserted y at position 6]
P 15 d=-1: 8 9 7 6 5 10 4 3 2 1 [10 inserted y at position 5]
P 16 d=-1: 8 9 7 6 10 5 4 3 2 1 [10 inserted y at position 4]
P 17 d=-1: 8 9 7 10 6 5 4 3 2 1 [10 inserted y at position 3]
P 18 d=-1: 8 9 10 7 6 5 4 3 2 1 [10 inserted y at position 2]
P 19 d=-1: 8 10 9 7 6 5 4 3 2 1 [10 inserted y at position 1]
P 20 d=-1: 10 8 9 7 6 5 4 3 2 1 [10 added to head y] [added to head, next dir = 1]
...
...
P 3628781 d= 1: 10 8 9 7 6 5 4 3 1 2 [10 added to head x] [added to head, next dir = 1]
P 3628782 d= 1: 8 10 9 7 6 5 4 3 1 2 [10 inserted x]
P 3628783 d= 1: 8 9 10 7 6 5 4 3 1 2 [10 inserted x]
P 3628784 d= 1: 8 9 7 10 6 5 4 3 1 2 [10 inserted x]
P 3628785 d= 1: 8 9 7 6 10 5 4 3 1 2 [10 inserted x]
P 3628786 d= 1: 8 9 7 6 5 10 4 3 1 2 [10 inserted x]
P 3628787 d= 1: 8 9 7 6 5 4 10 3 1 2 [10 inserted x]
P 3628788 d= 1: 8 9 7 6 5 4 3 10 1 2 [10 inserted x]
P 3628789 d= 1: 8 9 7 6 5 4 3 1 10 2 [10 inserted x]
P 3628790 d= 1: 8 9 7 6 5 4 3 1 2 10 [10 added to tail x] [added to tail, next dir = -1]
P 3628791 d=-1: 9 8 7 6 5 4 3 1 2 10 [10 added to tail y] [added to tail, next dir = -1]
P 3628792 d=-1: 9 8 7 6 5 4 3 1 10 2 [10 inserted y at position 8]
P 3628793 d=-1: 9 8 7 6 5 4 3 10 1 2 [10 inserted y at position 7]
P 3628794 d=-1: 9 8 7 6 5 4 10 3 1 2 [10 inserted y at position 6]
P 3628795 d=-1: 9 8 7 6 5 10 4 3 1 2 [10 inserted y at position 5]
P 3628796 d=-1: 9 8 7 6 10 5 4 3 1 2 [10 inserted y at position 4]
P 3628797 d=-1: 9 8 7 10 6 5 4 3 1 2 [10 inserted y at position 3]
P 3628798 d=-1: 9 8 10 7 6 5 4 3 1 2 [10 inserted y at position 2]
P 3628799 d=-1: 9 10 8 7 6 5 4 3 1 2 [10 inserted y at position 1]
P 3628800 d=-1: 10 9 8 7 6 5 4 3 1 2 [10 added to head y] [added to head, next dir = 1]
Postscript: I was wondering, if I wanted to store the list of sequences, how to compress them. Up to a certain level, (16 bells) I could put two elements in a single byte. Then I thought I could simply store which two elements have been swapped. So an array of which elements to swap. I did a small test, this is for 4 elements, with the swapped elements in square brackets:
P 1 d= 1: 4 3 2 1
P 2 d= 1: 3 4 2 1 [ 0 1 ] elements in positions 0 and 1 swapped
P 3 d= 1: 3 2 4 1 [ 1 2 ] elements in positions 1 and 2 swapped
P 4 d= 1: 3 2 1 4 [ 2 3 ]
P 5 d=-1: 2 3 1 4 [ 0 1 ]
P 6 d=-1: 2 3 4 1 [ 2 3 ]
P 7 d=-1: 2 4 3 1 [ 1 2 ]
P 8 d=-1: 4 2 3 1 [ 0 1 ]
P 9 d= 1: 4 2 1 3 [ 2 3 ]
P 10 d= 1: 2 4 1 3 [ 0 1 ]
P 11 d= 1: 2 1 4 3 [ 1 2 ]
P 12 d= 1: 2 1 3 4 [ 2 3 ]
P 13 d=-1: 1 2 3 4 [ 0 1 ]
P 14 d=-1: 1 2 4 3 [ 2 3 ]
P 15 d=-1: 1 4 2 3 [ 1 2 ]
P 16 d=-1: 4 1 2 3 [ 0 1 ]
P 17 d= 1: 4 1 3 2 [ 2 3 ]
P 18 d= 1: 1 4 3 2 [ 0 1 ]
P 19 d= 1: 1 3 4 2 [ 1 2 ]
P 20 d= 1: 1 3 2 4 [ 2 3 ]
P 21 d=-1: 3 1 2 4 [ 0 1 ]
P 22 d=-1: 3 1 4 2 [ 2 3 ]
P 23 d=-1: 3 4 1 2 [ 1 2 ]
P 24 d=-1: 4 3 1 2 [ 0 1 ]
Then I wondered if there was a pattern in which elements get swapped. If I could generate that pattern I could have a newer faster algorithm.
Here is the table above, just showing the swaps:
P 1
P 2 [ 0 1 ]
P 3 [ 1 2 ]
P 4 [ 2 3 ]
P 5 [ 0 1 ]
P 6 [ 2 3 ]
P 7 [ 1 2 ]
P 8 [ 0 1 ]
P 9 [ 2 3 ]
P 10 [ 0 1 ]
P 11 [ 1 2 ]
P 12 [ 2 3 ]
P 13 [ 0 1 ]
P 14 [ 2 3 ]
P 15 [ 1 2 ]
P 16 [ 0 1 ]
P 17 [ 2 3 ]
P 18 [ 0 1 ]
P 19 [ 1 2 ]
P 20 [ 2 3 ]
P 21 [ 0 1 ]
P 22 [ 2 3 ]
P 23 [ 1 2 ]
P 24 [ 0 1 ]
I don't currently have the will power or brain power to determine the pattern in the swaps, but worth looking into. Also note that even a 16 element sequence would still only have two elements swapped each time.
