+- Forums - Open Redstone Engineers (https://forum.openredstone.org)
+-- Forum: ORE General (https://forum.openredstone.org/forum-39.html)
+--- Forum: Projects & Inventions (https://forum.openredstone.org/forum-19.html)
+---- Forum: Completed Projects (https://forum.openredstone.org/forum-21.html)
+---- Thread: Subfactorials - an alternative benchmarking algorithm (/thread-14556.html)
Subfactorials - an alternative benchmarking algorithm - tokumei - 09-07-2018
As part of a challenge posted to r/dailyprogrammer a couple of days ago, I derived an algorithm for the subfactorial, which is similar in definition to the factorial. The subfactorial of n (!n) is the number of permutations of an ordered collection of n unique values such that no value retains its original position (these special permutations are called derangements). Intuitively, we can say that !n is always less than n! since there will always be exclusions, hence the name "subfactorial".
We can define some base cases:
subf(0) = 1 (we say that "all" of the elements in an empty collection are out of place, so we count the empty collection itself once).
subf(1) = 0 (a collection of length 1 can not be permutated, and therefore has no derangements).
And we can also derive a recursive definition. Let's say for a subfactorial of n, we append element n onto a collection of n-1 values. Element n is currently in-place, and so we must swap it with any of the other n-1 values which will then guarantee that both values are not in their original place. We can either ensure that all n-1 values are out of place (subf(n-1) cases) and swap with any of them (n-1 cases), making a term of (n-1) * subf(n-1), or we can ensure n-2 of the n-1 values are out of place (subf(n-2) cases), leaving one in-place that we swap with the new value to make out-of-place (n-1 cases), creating a second term of (n-1) * subf(n-2).
With some factoring, we get the following recursive definition:
subf(n) = (n - 1) * (subf(n - 1) + subf(n - 2))
Note how similar it is to Fibonacci, with the main difference being the multiplication at every level of recursion. Like Fibonacci, the complexity of this definition is 2^n, but it can easily be simplified into a linear, sequential algorithm where we compute starting at the base cases, going bottom-up instead of top-down.
Some more simple examples:
subf(2) = 1 (for an ordered collection [1, 2], the one valid derangement is [2, 1])
subf(3) = 2 (for an ordered collection [1, 2, 3], the valid derangemnets are [3, 1, 2] and [2, 3, 1]).
Because of its similarity to the Fibonacci algorithms, I think this may be suitable as a benchmark program in some cases, especially where hardware multiplication may be implemented. It should be noted that the subfactorial approximates the factorial function, meaning it grows faster than exponential rate (which is used to approximate Fibonacci). By !6 we reach 265, which is out of the 8-bit range, and even more quickly, !9 surpasses the size of a 16-bit integer. Regardless, I found it very interesting and potentially useful in some case.
RE: Subfactorials - an alternative benchmarking algorithm - tokumei - 09-07-2018
Also holy crap, it's been a while since I checked in. Forum looks great, and I miss designing circuits on the server. Unfortunately, I think I'm done with redstone, but my endeavors with circuit simulators in general are certainly not over. Some of you may know that I started writing a voxel-based game framework this summer, and I've been making slow but steady progress toward my end goal, which is a fully FLOSS, rewritable, event-driven, modular, plugin-able, [insert buzz-word here] "game" where anyone can easily make the voxel simulation behave however they want with a little bit of scripting.
With that power, I'm going to either design my own wiring simulation or stabilize and recreate the basic redstone mechanics from Minecraft. One of the things that drove me away from using redstone is the instability; I feel like I can never get the timing right, or I'll alter something somewhere else and it changes the behavior drastically. That's partly due to redstone being a secondary feature, partly due to the buggy spaghet that the Minecraft has been from the beginning, and partly due to my own refusal to try to learn and work around the quirks. It's obviously possible; I see many of you doing great things, and more popular groups like scicraft who study the game mechanics closely, learning how to "exploit" them to make the most efficient farms and diagnosing bugs/instabilities to reliably work around them. I just don't think like that; I'd much rather learn from the core design/concepts of the things that exist and gain experience by implementing it better.
With all of that being said, I do love what this community has done, I'm glad I was able to contribute where I could, and I'm hoping to stay in touch and work alongside many of you in future projects. Of course, I'll still post relevant updates here every once in a while, and I'll also soon resurrect my blog (speaking of which, I really need to renew those certificates...)