3 ms·
If you enjoy this sort of thing, it is also the start of Knuth's volume 4. In it, he goes over many different schemes of generating things. My favorites are t
by taeric 10y ago
If you enjoy this sort of thing, it is also the start of Knuth's volume 4. In it, he goes over many different schemes of generating things.
My favorites are the ones he calls "loopless" since they do not have a loop during each iteration of the algorithm. So, in this example, there is no need for the filter line that will ultimately have to loop (or hash or something else not trivial) to find the items to filter out). In particular, to generate all permutations of binary digits requires something like 4 assignments and one test for each iteration.
The ridiculously interesting ones are based on De Bruijn sequences. Basically, think if you have a combination lock that constantly shifts in 1 character when you type. Is it possible to test all combinations of digits without "wasting" a keypress?
- theoh 10y agoThe Wikipedia page for de Bruijn sequences is pretty good. https://en.wikipedia.org/wiki/De_Bruijn_sequence https://en.wikipedia.org/wiki/De_Bruijn_sequence My personal interest is in generalized LFSRs, which can be used to generate de Bruijn sequences. From the wiki page for LFSR: "Non-binary Galois LFSR Binary Galois LFSRs like the ones shown above can be generalized to any q-ary alphabet {0, 1, ..., q − 1} (e.g., for binary, q = 2, and the alphabet is simply {0, 1}). In this case, the exclusive-or component is generalized to addition modulo-q (note that XOR is addition modulo 2), and the feedback bit (output bit) is multiplied (modulo-q) by a q-ary value, which is constant for each specific tap point. Note that this is also a generalization of the binary case, where the feedback is multiplied by either 0 (no feedback, i.e., no tap) or 1 (feedback is present). Given an appropriate tap configuration, such LFSRs can be used to generate Galois fields for arbitrary prime values of q."