Latin Squares in reduced form: Difference between revisions

Content added Content deleted

Inline

@@ Line 1,334: / Line 1,334: @@
 </pre>
 The only way to complete the tasks requirement to produce a table is with another language. Ruby has the ability to run an external program, capture the output, and text handling ability to format it to this tasks requirements. Othe scripting languages are available.
+=={{header|Nim}}==
+{{trans|Go, Python, D, Kotlin}}
+We use the Go algorithm but have chosen to create two types, Row and matrix, to simulate sequences starting at index 1. So, the indexes and tests are somewhat different.
+<lang Nim>import algorithm, math, sequtils, strformat
+type
+  # Row managed as a sequence of ints with base index 1.
+  Row = object
+    value: seq[int]
+  # Matrix managed as a sequence of rows with base index 1.
+  Matrix = object
+    value: seq[Row]
+func newRow(n: Natural = 0): Row =
+  ## Create a new row of length "n".
+  Row(value: newSeq[int](n))
+# Create a new matrix of length "n" containing rows of length "p".
+func newMatrix(n, p: Natural = 0): Matrix = Matrix(value: newSeqWith(n, newRow(p)))
+# Functions for rows.
+func `[]`(r: var Row; i: int): var int = r.value[i - 1]
+func `[]=`(r: var Row; i, n: int) = r.value[i - 1] = n
+func sort(r: var Row; low, high: Positive) =
+  r.value.toOpenArray(low - 1, high - 1).sort()
+func `$`(r: Row): string = ($r.value)[1..^1]
+# Functions for matrices.
+func `[]`(m: Matrix; i: int): Row = m.value[i - 1]
+func `[]`(m: var Matrix; i: int): var Row = m.value[i - 1]
+func `[]=`(m: var Matrix; i: int; r: Row) = m.value[i - 1] = r
+func high(m: Matrix): Natural = m.value.len
+func add(m: var Matrix; r: Row) = m.value.add r
+func `$`(m: Matrix): string =
+  for row in m.value: result.add $row & '\n'
+func dList(n, start: Positive): Matrix =
+  ## Generate derangements of first 'n' numbers, with 'start' in first place.
+  var a = Row(value: toSeq(1..n))
+  swap a[1], a[start]
+  a.sort(2, n)
+  let first = a[2]
+  var r: Matrix
+  func recurse(last: int) =
+    ## Recursive closure permutes a[2..^1].
+    if last == first:
+      # Bottom of recursion. You get here once for each permutation.
+      # Test if permutation is deranged.
+      for i in 2..n:
+        if a[i] == i: return  # No: ignore it.
+      r.add a
+      return
+    for i in countdown(last, 2):
+      swap a[i], a[last]
+      recurse(last - 1)
+      swap a[i], a[last]
+  recurse(n)
+  result = r
+proc reducedLatinSquares(n: Positive; print: bool): int =
+  if n == 1:
+    if print: echo [1]
+    return 1
+  var rlatin = newMatrix(n, n)
+  # Initialize first row.
+  for i in 1..n: rlatin[1][i] = i
+  var count = 0
+  proc recurse(i: int) =
+    let rows = dList(n, i)
+    for r in 1..rows.high:
+      block inner:
+        rlatin[i] = rows[r]
+        for k in 1..<i:
+          for j in 2..n:
+            if rlatin[k][j] == rlatin[i][j]:
+              if r < rows.high: break inner
+              if i > 2: return
+        if i < n:
+          recurse(i + 1)
+        else:
+          inc count
+          if print: echo rlatin
+  # Remaining rows.
+  recurse(2)
+  result = count
+when isMainModule:
+  echo "The four reduced latin squares of order 4 are:"
+  discard reducedLatinSquares(4, true)
+  echo "The size of the set of reduced latin squares for the following orders"
+  echo "and hence the total number of latin squares of these orders are:"
+  for n in 1..6:
+    let size = reducedLatinSquares(n, false)
+    let f = fac(n - 1)^2 * n * size
+    echo &"Order {n}: Size {size:<4} x {n}! x {n - 1}! => Total {f}"</lang>
+{{out}}
+<pre>The four reduced latin squares of order 4 are:
+[1, 2, 3, 4]
+[2, 1, 4, 3]
+[3, 4, 1, 2]
+[4, 3, 2, 1]
+[1, 2, 3, 4]
+[2, 1, 4, 3]
+[3, 4, 2, 1]
+[4, 3, 1, 2]
+[1, 2, 3, 4]
+[2, 4, 1, 3]
+[3, 1, 4, 2]
+[4, 3, 2, 1]
+[1, 2, 3, 4]
+[2, 3, 4, 1]
+[3, 4, 1, 2]
+[4, 1, 2, 3]
+The size of the set of reduced latin squares for the following orders
+and hence the total number of latin squares of these orders are:
+Order 1: Size 1    x 1! x 0! => Total 1
+Order 2: Size 1    x 2! x 1! => Total 2
+Order 3: Size 1    x 3! x 2! => Total 12
+Order 4: Size 4    x 4! x 3! => Total 576
+Order 5: Size 56   x 5! x 4! => Total 161280
+Order 6: Size 9408 x 6! x 5! => Total 812851200</pre>
 =={{header|Perl}}==