What different algorithms have you developed in Scala?
Software Engineer, Ignacio Gallego Sagastume created this algorithm to help him generate Random Latin Squares. Let's find out how efficient it is and how it works!
I called this algorithm "the SeqGen (sequential-generation type) with a replacement chain conflict resolution strategy" or more succinctly "SeqGen with replacement chain", or just "the replacement chain algorithm". Its main advantage is that is faster than (by a factor of around 2) the Jacobson & Matthews' (J&M) algorithm, the most widely known and accepted algorithm in the area. On the other hand, its main disadvantage is that it is not uniformly distributed (as the J&M's), but its distribution is acceptable under certain conditions, as it is approximately uniform.
2 4 3 1
4 3 1 2
3 1 2 4
LSs are used for many applications, for example for games, combinatorics and some cryptographic applications.
A remarkable property is that L(n), the number of different LSs of order n, is only known when n<=11. For larger orders, the number L(n) is unknown up to now, and it is so high that only upper and lower bounds can be given:
The Scala algorithm
We start with an empty matrix, a matrix full of 0s or nulls, as you prefer. We begin by row with index 0, extracting a random number one at a time. When we finish the row 0, we can continue with row 1, in order. As the matrix is immutable, we need a function that takes a partially completed LS with n rows filled and a row index and returns a new LS with n+1 rows completed. There is a theorem that says that this can always be done, row by row, up to the last row.
How can we model a computation like this in FP? This was the first "eureka" moment: using the foldlLeft function and the empty matrix as the base element. This is the "main" method to generate an LS:
The getEmptyMatrix auxiliary method is simply:
We continue with the generateRow method:
Then, if the row is incomplete, we try to generate the element in position (i,j) randomly, possibly causing a conflict (repetition) in that position with previously generated elements in the same row. If a conflict is created (there is not another possibility in that position) we trigger the resolution strategy called "replacement chain". Basically, we make room for the element elem, taking into account, that this chain of replacements can fail. So, we repeat the procedure until we can accommodate the element elem without repetitions. In that case, we can continue the generation of the element in position (i, j + 1) recursively.
We highlight here the creation of a new control structure retryUntilSucceed that repeats an operation in case of an exception, extending in a way the Scala language: