Ask HN: Implications of (super)permutations on software testing?
Hi HN.

Junior software developer here.

I recently stumbled upon the minimal superpermutation problem and I'm trying to figure out what the implications are for software developers when it comes to effectively testing their code.

(Below is an explorative example in an attempt to try and get more clarity about this. Perhaps I'm looking at it in the wrong way, hope some people can share their view on this. Questions at end of post.)

The best example to illustrate what I mean by that would be to use a complex online videogame as the example of a software application in need of effective testing.

Such a videogame, to me, consists out of a considerable amount of active and mutable state which is exhaustively queried and constantly in flux.

Consider that an optimal amount of coupling & cohesion is pursued but that due to the videogame's inherent complexity, developmental time constraints, managerial decisions, incompetency, .., the development team inevitably introduces mistakes in this regard.

Envision a scenario where a single state entry can have its value queried and altered by n actors due to some of the entry's characteristics in relation to other entries' characteristics resulting in an implied need for relational connectivity.

A simple example of such an entry would be the state of a particular entity represented by an enum.

With testing in mind, imagine that in order to provide security to block prohibited state transitions a table could be made containing the permitted state transitions.

Sounds like a good solution when there are not a lot of possible states defined in the enum. Sounds even better when you realize that the table is an allowlist and that not all transitions have to be included. Sounds great when you're only considering single-step state changes.

However such a table is not aware of the context encapsulated within an actor, the actor may alter the state as permitted by the table, even when it may not be the appropriate state to change to, e.g. due to a logical error.

My interpretation is then that in order for the transition table to become more effective in preventing undesired transitions, it is implied that it must contain the constituents of an actor's context which are determined to be in some way involved in the logic which decides which state the enum should transition to.

It seems to me that including those variables in the table would lead to a large amount of scenarios to consider (aka write tests for). It becomes even more tricky when those actors have some sort of relationship with eachother, and even trickier when they themselves have dependencies.

Then there's the possibility that you do not want to perform a state transition you have performed before, that you do not want to do that when one or more actors has a certain state, and so forth.

Whether such a table would have any value beyond a certain amount of columns, I am not certain. But this line of thinking made me think of permutations (if you'd be willing to have subsets) and makes me wonder whether the minimal superpermutation problem has any value when talking about testing software?

In my experience so far writing unit tests I can usually assert that all paths have been covered, but once in a while I'll come across a case where testing all possible combinations becomes a near impossible task.

While searching I came across "combinatorial testing", seems relevant but still fail to see how it all ties together?

https://en.wikipedia.org/wiki/Superpermutation

https://personal.utdallas.edu/~ewong/SE6367/03-Lecture/29-A-Combinatorial-Testing-by-Kuhn.pdf