# Memex: Today's Interesting Links (SubEthaEdit, generating permutations, proofs) (2024-01-17)

**URL:** <https://pluralist.net/t/memex-todays-interesting-links-subethaedit-generating-permutations-proofs-2024-01-17/47>\
**Category:** breadcrumbs\
**Created:** [January 18, 2024, 12:14am UTC](https://pluralist.net/t/memex-todays-interesting-links-subethaedit-generating-permutations-proofs-2024-01-17/47 "2024-01-18T00:14:06Z")\
**Posts on this page:** 1\
**Page:** 1

<div class="post-metadata">

**Author:** ![delyan](https://pluralist.net/user_avatar/pluralist.net/delyan/32/245_2.png) [@delyan](https://pluralist.net/u/delyan)\
**Post date:** [January 18, 2024, 12:14am UTC](https://pluralist.net/t/memex-todays-interesting-links-subethaedit-generating-permutations-proofs-2024-01-17/47/1 "2024-01-18T00:14:06Z")

</div>

- [SubEthaEdit](https://subethaedit.net/) is a fascinating text editor - minimalist and one with interesting history. The editor is OSS, MIT license, and [available on GitHub](https://github.com/subethaedit/SubEthaEdit).
  - [example source - Presence Manager](https://github.com/subethaedit/SubEthaEdit/blob/a3fec93223275ff758d7035aceefd94ce8ad1874/SubEthaEdit-Mac/Source/TCMMillionMonkeys/TCMMMPresenceManager.m#L554)
  - SubEthaEdit relies on the [“Blocks Extensible Exchange Protocol” (BEEP)](http://www.beepcore.org/subethaedit.html).

- Let’s say that you wanted to write some C++ to generate all permutations for `char A[4] = {'A', 'B', 'C', 'D'};`. How do you go about that?
  - the easiest way turns out is to leverage `<algorithm>`:

```C++
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    int N=4; /* number of letters */
    char A[N-1] = {'A', 'B', 'C', 'D'};
    sort(A, A + N); /* requirement: this needs to be sorted */
    do {
        for (int i = 0; i < N; ++i) cout << A[i] << " "; cout << endl;
    } while (std::next_permutation(A, A + 4));
    return 0;
}

```

- I would have preferred some recursive approach and not using `<algorithm>`:

```c++
#include <iostream>
#include <vector>
using namespace std;
// Find all the permutations of the 4 letters below.
char A[4] = {'A','B','C','D'};
bool used[4]; // tag letters from above when used so there's no reuse
vector<char> perm;
void permute() {
	if (perm.size() == 4) {
        for(auto x : perm) { cout << x; } cout << endl; /* print it */
		return;
	}
    for (int i=0; i<4; i++) {
        if(used[i]) continue; /* permutation: no reuse */
        perm.push_back(A[i]); /* add current character */
        used[i] = true; /* mark it as used */
        permute(); /* >>> go again <<< */
        perm.pop_back(); /* free the character */
        used[i] = false; /* mark it unused */
    }
}

int main() {
	permute();
}

```

- Speaking of recursion - I love how great IBM’s docs are. Here is something amazing:  
[Mastering recursive programming: Learning recursion yields maintainable, consistent, provably correct code](https://developer.ibm.com/articles/l-recurs/) by Jonathan Bartlett June 16, 2005 or [Inside Memory Management](https://developer.ibm.com/tutorials/l-memory/).
- Turns out there exist a non-recursive algorithm discovered/invented/proposed by [B. R. Heap in 1963](https://en.wikipedia.org/wiki/Heap%27s_algorithm). Great LaTeX rendering of the algorithm [on Baeldung](https://www.baeldung.com/cs/array-generate-all-permutations#2-non-recursive-heaps-algorithm):  
 ![image](https://pluralist.net/uploads/default/original/1X/a1d3ba039579573dbdae6447c2e616fefc2bd057.png)
- But the field of permutations has been studied extensively… so why stop here - take a look at Steinhaus–Johnson–Trotter algorithm as well - [wikipedia](https://en.wikipedia.org/wiki/Steinhaus%E2%80%93Johnson%E2%80%93Trotter_algorithm) - [**BIT I5(1975), 158-164  
Asimplifiedloop-Free Algorithm For Generating Permutations by Nachum Dershowitz**](https://www.cs.tau.ac.il//~nachumd/papers/BIT.pdf).
  - proof of the Steinhaus–Johnson–Trotter algorithm