0 people like it.

Generic Latin Square generator

A type which generates a Latin Square - ie. an n x n array where no value is repeated in any one row or column. Useful in experimental design and some forms of testing. The argument is generic so you can generate a Latin Square of ints, floats, strings, dates, classes etc. (Needs some optimisation - this is a first cut!)

  1: 
  2: 
  3: 
  4: 
  5: 
  6: 
  7: 
  8: 
  9: 
 10: 
 11: 
 12: 
 13: 
 14: 
 15: 
 16: 
 17: 
 18: 
 19: 
 20: 
 21: 
 22: 
 23: 
 24: 
 25: 
 26: 
 27: 
 28: 
 29: 
 30: 
 31: 
 32: 
 33: 
 34: 
 35: 
 36: 
 37: 
 38: 
 39: 
 40: 
 41: 
 42: 
 43: 
 44: 
 45: 
 46: 
 47: 
 48: 
 49: 
 50: 
 51: 
 52: 
 53: 
 54: 
 55: 
 56: 
 57: 
 58: 
 59: 
 60: 
 61: 
 62: 
 63: 
 64: 
 65: 
 66: 
 67: 
 68: 
 69: 
 70: 
 71: 
 72: 
 73: 
 74: 
 75: 
 76: 
 77: 
 78: 
 79: 
 80: 
 81: 
 82: 
 83: 
 84: 
 85: 
 86: 
 87: 
 88: 
 89: 
 90: 
 91: 
 92: 
 93: 
 94: 
 95: 
 96: 
 97: 
 98: 
 99: 
100: 
101: 
102: 
103: 
104: 
105: 
106: 
107: 
108: 
109: 
110: 
111: 
112: 
113: 
114: 
115: 
116: 
117: 
118: 
119: 
120: 
121: 
122: 
123: 
124: 
125: 
126: 
127: 
128: 
129: 
130: 
131: 
132: 
133: 
134: 
135: 
136: 
137: 
138: 
139: 
140: 
141: 
142: 
143: 
144: 
145: 
146: 
147: 
148: 
149: 
150: 
151: 
152: 
153: 
154: 
155: 
156: 
157: 
158: 
159: 
160: 
161: 
162: 
163: 
164: 
165: 
166: 
167: 
168: 
169: 
170: 
171: 
172: 
173: 
174: 
175: 
176: 
177: 
178: 
179: 
180: 
181: 
182: 
183: 

#if INTERACTIVE
#r "System.Drawing"
#endif

module LatinSquaresDemo =

    module LatinSquares = 
        open System

        // Generate a Latin Square, populating with the specified values. To generate a 'reduced' Latin Square
        // send in the values sorted; otherwise randomise the values before calling.
        let inline LatinSquare(values : ^a[]) =
            let n = values |> Array.length
            let r = new Random()
            let scramble = Array.sortBy (fun _ -> r.Next(n))

            let hasConflicts (a : ^a option[,]) r =
                let (=?) (m : ^a option) (n : ^a option) =
                       (n.IsNone && m.IsNone)
                    || (n.IsSome && m.IsSome && (n.Value = m.Value))
                let mutable conflicts = false
                for c in 0..n-1 do
                    let bottom = a.[r,c]
                    for r' in 0..r-1 do
                        if bottom =? a.[r',c] then
                            conflicts <- true
                conflicts

            let arr = Array2D.init n n (fun _ _ -> None)

            values |> Array.iteri (fun c x -> arr.[0, c] <- Some(x))

            for r in 1..n-1 do
                let mutable conflicts = true
                while conflicts do
                    values |> scramble |> Array.iteri (fun c x -> arr.[r,c] <- Some(x))
                    conflicts <- hasConflicts arr r

            arr |> Array2D.map (fun e -> e.Value)

    module Demo =

        open System
        open System.Drawing
        open LatinSquares

        // [[1; 2; 3]
        //  [2; 3; 1]
        //  [3; 1; 2]]
        let ints3x3 = LatinSquare([|1..3|])

        // [[1; 2; 3; 4; 5; 6; 7]
        //  [5; 4; 2; 1; 6; 7; 3]
        //  [4; 6; 5; 7; 1; 3; 2]
        //  [7; 1; 4; 3; 2; 5; 6]
        //  [3; 7; 1; 6; 4; 2; 5]
        //  [6; 5; 7; 2; 3; 1; 4]
        //  [2; 3; 6; 5; 7; 4; 1]]
        let ints7x7 = LatinSquare([|1..7|])

        // [[1.5; 2.0; 2.5; 3.0; 3.5; 4.0; 4.5]
        //  [3.5; 3.0; 2.0; 1.5; 4.0; 4.5; 2.5]
        //  [3.0; 4.0; 3.5; 4.5; 1.5; 2.5; 2.0]
        //  [4.5; 1.5; 3.0; 2.5; 2.0; 3.5; 4.0]
        //  [2.5; 4.5; 1.5; 4.0; 3.0; 2.0; 3.5]
        //  [4.0; 3.5; 4.5; 2.0; 2.5; 1.5; 3.0]
        //  [2.0; 2.5; 4.0; 3.5; 4.5; 3.0; 1.5]]
        let floats7x7 = LatinSquare([|1.5..0.5..4.5|])

        //[[02/01/2013 00:00:00; 03/01/2013 00:00:00; 04/01/2013 00:00:00;
        //    05/01/2013 00:00:00; 06/01/2013 00:00:00; 07/01/2013 00:00:00;
        //    08/01/2013 00:00:00]
        //    [06/01/2013 00:00:00; 05/01/2013 00:00:00; 03/01/2013 00:00:00;
        //    02/01/2013 00:00:00; 07/01/2013 00:00:00; 08/01/2013 00:00:00;
        //    04/01/2013 00:00:00]
        //    [05/01/2013 00:00:00; 07/01/2013 00:00:00; 06/01/2013 00:00:00;
        //    08/01/2013 00:00:00; 02/01/2013 00:00:00; 04/01/2013 00:00:00;
        //    03/01/2013 00:00:00]
        //    [08/01/2013 00:00:00; 02/01/2013 00:00:00; 05/01/2013 00:00:00;
        //    04/01/2013 00:00:00; 03/01/2013 00:00:00; 06/01/2013 00:00:00;
        //    07/01/2013 00:00:00]
        //    [04/01/2013 00:00:00; 08/01/2013 00:00:00; 02/01/2013 00:00:00;
        //    07/01/2013 00:00:00; 05/01/2013 00:00:00; 03/01/2013 00:00:00;
        //    06/01/2013 00:00:00]
        //    [07/01/2013 00:00:00; 06/01/2013 00:00:00; 08/01/2013 00:00:00;
        //    03/01/2013 00:00:00; 04/01/2013 00:00:00; 02/01/2013 00:00:00;
        //    05/01/2013 00:00:00]
        //    [03/01/2013 00:00:00; 04/01/2013 00:00:00; 07/01/2013 00:00:00;
        //    06/01/2013 00:00:00; 08/01/2013 00:00:00; 05/01/2013 00:00:00;
        //    02/01/2013 00:00:00]]
        let dates7x7 = LatinSquare([|1..7|] |> Array.map (fun d -> DateTime(2013, 1, 1).AddDays(d |> float)))

        // [["Harder"; "Better"; "Faster"; "Stronger"]
        //  ["Stronger"; "Harder"; "Better"; "Faster"]
        //  ["Faster"; "Stronger"; "Harder"; "Better"]
        //  ["Better"; "Faster"; "Stronger"; "Harder"]]
        let daftPunk = LatinSquare([|"Harder"; "Better"; "Faster"; "Stronger"|])

        //<html>
        //  <table style="border:2px solid #404040; border-collapse: collapse; ">
        //    <tr>
        //      <td style="width:20px; height:22px; border:2px solid #404040; border-collapse: collapse; background-color:Purple"></td>
        //      <td style="width:20px; height:22px; border:2px solid #404040; border-collapse: collapse; background-color:LightBlue"></td>
        //      <td style="width:20px; height:22px; border:2px solid #404040; border-collapse: collapse; background-color:DarkGreen"></td>
        //      <td style="width:20px; height:22px; border:2px solid #404040; border-collapse: collapse; background-color:Red"></td>
        //      <td style="width:20px; height:22px; border:2px solid #404040; border-collapse: collapse; background-color:Brown"></td>
        //      <td style="width:20px; height:22px; border:2px solid #404040; border-collapse: collapse; background-color:Yellow"></td>
        //      <td style="width:20px; height:22px; border:2px solid #404040; border-collapse: collapse; background-color:DarkBlue"></td>
        //    </tr>
        //    <tr>
        //      <td style="width:20px; height:22px; border:2px solid #404040; border-collapse: collapse; background-color:Yellow"></td>
        //      <td style="width:20px; height:22px; border:2px solid #404040; border-collapse: collapse; background-color:DarkBlue"></td>
        //      <td style="width:20px; height:22px; border:2px solid #404040; border-collapse: collapse; background-color:Brown"></td>
        //      <td style="width:20px; height:22px; border:2px solid #404040; border-collapse: collapse; background-color:DarkGreen"></td>
        //      <td style="width:20px; height:22px; border:2px solid #404040; border-collapse: collapse; background-color:Red"></td>
        //      <td style="width:20px; height:22px; border:2px solid #404040; border-collapse: collapse; background-color:Purple"></td>
        //      <td style="width:20px; height:22px; border:2px solid #404040; border-collapse: collapse; background-color:LightBlue"></td>
        //    </tr>
        //    <tr>
        //      <td style="width:20px; height:22px; border:2px solid #404040; border-collapse: collapse; background-color:Brown"></td>
        //      <td style="width:20px; height:22px; border:2px solid #404040; border-collapse: collapse; background-color:Red"></td>
        //      <td style="width:20px; height:22px; border:2px solid #404040; border-collapse: collapse; background-color:LightBlue"></td>
        //      <td style="width:20px; height:22px; border:2px solid #404040; border-collapse: collapse; background-color:Purple"></td>
        //      <td style="width:20px; height:22px; border:2px solid #404040; border-collapse: collapse; background-color:DarkBlue"></td>
        //      <td style="width:20px; height:22px; border:2px solid #404040; border-collapse: collapse; background-color:DarkGreen"></td>
        //      <td style="width:20px; height:22px; border:2px solid #404040; border-collapse: collapse; background-color:Yellow"></td>
        //    </tr>
        //    <tr>
        //      <td style="width:20px; height:22px; border:2px solid #404040; border-collapse: collapse; background-color:LightBlue"></td>
        //      <td style="width:20px; height:22px; border:2px solid #404040; border-collapse: collapse; background-color:Purple"></td>
        //      <td style="width:20px; height:22px; border:2px solid #404040; border-collapse: collapse; background-color:Red"></td>
        //      <td style="width:20px; height:22px; border:2px solid #404040; border-collapse: collapse; background-color:Yellow"></td>
        //      <td style="width:20px; height:22px; border:2px solid #404040; border-collapse: collapse; background-color:DarkGreen"></td>
        //      <td style="width:20px; height:22px; border:2px solid #404040; border-collapse: collapse; background-color:DarkBlue"></td>
        //      <td style="width:20px; height:22px; border:2px solid #404040; border-collapse: collapse; background-color:Brown"></td>
        //    </tr>
        //    <tr>
        //      <td style="width:20px; height:22px; border:2px solid #404040; border-collapse: collapse; background-color:DarkGreen"></td>
        //      <td style="width:20px; height:22px; border:2px solid #404040; border-collapse: collapse; background-color:Yellow"></td>
        //      <td style="width:20px; height:22px; border:2px solid #404040; border-collapse: collapse; background-color:DarkBlue"></td>
        //      <td style="width:20px; height:22px; border:2px solid #404040; border-collapse: collapse; background-color:Brown"></td>
        //      <td style="width:20px; height:22px; border:2px solid #404040; border-collapse: collapse; background-color:LightBlue"></td>
        //      <td style="width:20px; height:22px; border:2px solid #404040; border-collapse: collapse; background-color:Red"></td>
        //      <td style="width:20px; height:22px; border:2px solid #404040; border-collapse: collapse; background-color:Purple"></td>
        //    </tr>
        //    <tr>
        //      <td style="width:20px; height:22px; border:2px solid #404040; border-collapse: collapse; background-color:Red"></td>
        //      <td style="width:20px; height:22px; border:2px solid #404040; border-collapse: collapse; background-color:Brown"></td>
        //      <td style="width:20px; height:22px; border:2px solid #404040; border-collapse: collapse; background-color:Yellow"></td>
        //      <td style="width:20px; height:22px; border:2px solid #404040; border-collapse: collapse; background-color:DarkBlue"></td>
        //      <td style="width:20px; height:22px; border:2px solid #404040; border-collapse: collapse; background-color:Purple"></td>
        //      <td style="width:20px; height:22px; border:2px solid #404040; border-collapse: collapse; background-color:LightBlue"></td>
        //      <td style="width:20px; height:22px; border:2px solid #404040; border-collapse: collapse; background-color:DarkGreen"></td>
        //    </tr>
        //    <tr>
        //      <td style="width:20px; height:22px; border:2px solid #404040; border-collapse: collapse; background-color:DarkBlue"></td>
        //      <td style="width:20px; height:22px; border:2px solid #404040; border-collapse: collapse; background-color:DarkGreen"></td>
        //      <td style="width:20px; height:22px; border:2px solid #404040; border-collapse: collapse; background-color:Purple"></td>
        //      <td style="width:20px; height:22px; border:2px solid #404040; border-collapse: collapse; background-color:LightBlue"></td>
        //      <td style="width:20px; height:22px; border:2px solid #404040; border-collapse: collapse; background-color:Yellow"></td>
        //      <td style="width:20px; height:22px; border:2px solid #404040; border-collapse: collapse; background-color:Brown"></td>
        //      <td style="width:20px; height:22px; border:2px solid #404040; border-collapse: collapse; background-color:Red"></td>
        //    </tr>
        //  </table>
        //</html>
        let stainedGlassHTML =
            let colors = [| Color.Purple; Color.LightBlue; Color.DarkGreen; Color.Red; Color.Brown; Color.Yellow; Color.DarkBlue |]
            let n = colors |> Array.length

            let sb = new System.Text.StringBuilder()
            let (+~) line = sb.AppendLine(line) |> ignore

            "<html>" |> (+~)
            "  <table style=\"border:2px solid #404040; border-collapse: collapse; \">" |> (+~)

            LatinSquare(colors)
            |> Array2D.iteri (fun _ c panel -> if c = 0 then   "    <tr>" |> (+~)
                                               sprintf         "      <td style=\"width:20px; height:22px; border:2px solid #404040; border-collapse: collapse; background-color:%s\"></td>" panel.Name |> (+~)
                                               if c = n-1 then "    </tr>" |> (+~))
            "  </table>" |> (+~)
            "</html>" |> (+~)

            sb.ToString()
module LatinSquaresDemo

from Script
namespace System
val LatinSquare : values:'a [] -> 'a [,] (requires equality)

Full name: Script.LatinSquaresDemo.LatinSquares.LatinSquare
val values : 'a [] (requires equality)
val n : int
type Array =
  member Clone : unit -> obj
  member CopyTo : array:Array * index:int -> unit + 1 overload
  member GetEnumerator : unit -> IEnumerator
  member GetLength : dimension:int -> int
  member GetLongLength : dimension:int -> int64
  member GetLowerBound : dimension:int -> int
  member GetUpperBound : dimension:int -> int
  member GetValue : [<ParamArray>] indices:int[] -> obj + 7 overloads
  member Initialize : unit -> unit
  member IsFixedSize : bool
  ...

Full name: System.Array
val length : array:'T [] -> int

Full name: Microsoft.FSharp.Collections.Array.length
val r : Random
Multiple items
type Random =
  new : unit -> Random + 1 overload
  member Next : unit -> int + 2 overloads
  member NextBytes : buffer:byte[] -> unit
  member NextDouble : unit -> float

Full name: System.Random

--------------------
Random() : unit
Random(Seed: int) : unit
val scramble : ('a [] -> 'a []) (requires equality)
val sortBy : projection:('T -> 'Key) -> array:'T [] -> 'T [] (requires comparison)

Full name: Microsoft.FSharp.Collections.Array.sortBy
Random.Next() : int
Random.Next(maxValue: int) : int
Random.Next(minValue: int, maxValue: int) : int
val hasConflicts : ('a option [,] -> int -> bool) (requires equality)
val a : 'a option [,] (requires equality)
type 'T option = Option<'T>

Full name: Microsoft.FSharp.Core.option<_>
val r : int
val m : 'a option (requires equality)
val n : 'a option (requires equality)
property Option.IsNone: bool
property Option.IsSome: bool
property Option.Value: 'a
val mutable conflicts : bool
val c : int32
val bottom : 'a option (requires equality)
val r' : int32
val arr : 'a option [,] (requires equality)
module Array2D

from Microsoft.FSharp.Collections
val init : length1:int -> length2:int -> initializer:(int -> int -> 'T) -> 'T [,]

Full name: Microsoft.FSharp.Collections.Array2D.init
union case Option.None: Option<'T>
val iteri : action:(int -> 'T -> unit) -> array:'T [] -> unit

Full name: Microsoft.FSharp.Collections.Array.iteri
val c : int
val x : 'a (requires equality)
union case Option.Some: Value: 'T -> Option<'T>
val r : int32
val map : mapping:('T -> 'U) -> array:'T [,] -> 'U [,]

Full name: Microsoft.FSharp.Collections.Array2D.map
val e : 'a option (requires equality)
module Demo

from Script.LatinSquaresDemo
namespace System.Drawing
module LatinSquares

from Script.LatinSquaresDemo
val ints3x3 : int [,]

Full name: Script.LatinSquaresDemo.Demo.ints3x3
val ints7x7 : int [,]

Full name: Script.LatinSquaresDemo.Demo.ints7x7
val floats7x7 : float [,]

Full name: Script.LatinSquaresDemo.Demo.floats7x7
val dates7x7 : DateTime [,]

Full name: Script.LatinSquaresDemo.Demo.dates7x7
val map : mapping:('T -> 'U) -> array:'T [] -> 'U []

Full name: Microsoft.FSharp.Collections.Array.map
val d : int
Multiple items
type DateTime =
  struct
    new : ticks:int64 -> DateTime + 10 overloads
    member Add : value:TimeSpan -> DateTime
    member AddDays : value:float -> DateTime
    member AddHours : value:float -> DateTime
    member AddMilliseconds : value:float -> DateTime
    member AddMinutes : value:float -> DateTime
    member AddMonths : months:int -> DateTime
    member AddSeconds : value:float -> DateTime
    member AddTicks : value:int64 -> DateTime
    member AddYears : value:int -> DateTime
    ...
  end

Full name: System.DateTime

--------------------
DateTime()
   (+0 other overloads)
DateTime(ticks: int64) : unit
   (+0 other overloads)
DateTime(ticks: int64, kind: DateTimeKind) : unit
   (+0 other overloads)
DateTime(year: int, month: int, day: int) : unit
   (+0 other overloads)
DateTime(year: int, month: int, day: int, calendar: Globalization.Calendar) : unit
   (+0 other overloads)
DateTime(year: int, month: int, day: int, hour: int, minute: int, second: int) : unit
   (+0 other overloads)
DateTime(year: int, month: int, day: int, hour: int, minute: int, second: int, kind: DateTimeKind) : unit
   (+0 other overloads)
DateTime(year: int, month: int, day: int, hour: int, minute: int, second: int, calendar: Globalization.Calendar) : unit
   (+0 other overloads)
DateTime(year: int, month: int, day: int, hour: int, minute: int, second: int, millisecond: int) : unit
   (+0 other overloads)
DateTime(year: int, month: int, day: int, hour: int, minute: int, second: int, millisecond: int, kind: DateTimeKind) : unit
   (+0 other overloads)
Multiple items
val float : value:'T -> float (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.float

--------------------
type float = Double

Full name: Microsoft.FSharp.Core.float

--------------------
type float<'Measure> = float

Full name: Microsoft.FSharp.Core.float<_>
val daftPunk : string [,]

Full name: Script.LatinSquaresDemo.Demo.daftPunk
val stainedGlassHTML : string

Full name: Script.LatinSquaresDemo.Demo.stainedGlassHTML
val colors : Color []
type Color =
  struct
    member A : byte
    member B : byte
    member Equals : obj:obj -> bool
    member G : byte
    member GetBrightness : unit -> float32
    member GetHashCode : unit -> int
    member GetHue : unit -> float32
    member GetSaturation : unit -> float32
    member IsEmpty : bool
    member IsKnownColor : bool
    ...
  end

Full name: System.Drawing.Color
property Color.Purple: Color
property Color.LightBlue: Color
property Color.DarkGreen: Color
property Color.Red: Color
property Color.Brown: Color
property Color.Yellow: Color
property Color.DarkBlue: Color
val sb : Text.StringBuilder
namespace System.Text
Multiple items
type StringBuilder =
  new : unit -> StringBuilder + 5 overloads
  member Append : value:string -> StringBuilder + 18 overloads
  member AppendFormat : format:string * arg0:obj -> StringBuilder + 4 overloads
  member AppendLine : unit -> StringBuilder + 1 overload
  member Capacity : int with get, set
  member Chars : int -> char with get, set
  member Clear : unit -> StringBuilder
  member CopyTo : sourceIndex:int * destination:char[] * destinationIndex:int * count:int -> unit
  member EnsureCapacity : capacity:int -> int
  member Equals : sb:StringBuilder -> bool
  ...

Full name: System.Text.StringBuilder

--------------------
Text.StringBuilder() : unit
Text.StringBuilder(capacity: int) : unit
Text.StringBuilder(value: string) : unit
Text.StringBuilder(value: string, capacity: int) : unit
Text.StringBuilder(capacity: int, maxCapacity: int) : unit
Text.StringBuilder(value: string, startIndex: int, length: int, capacity: int) : unit
val line : string
Text.StringBuilder.AppendLine() : Text.StringBuilder
Text.StringBuilder.AppendLine(value: string) : Text.StringBuilder
val ignore : value:'T -> unit

Full name: Microsoft.FSharp.Core.Operators.ignore
val iteri : action:(int -> int -> 'T -> unit) -> array:'T [,] -> unit

Full name: Microsoft.FSharp.Collections.Array2D.iteri
val panel : Color
val sprintf : format:Printf.StringFormat<'T> -> 'T

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.sprintf
property Color.Name: string
Text.StringBuilder.ToString() : string
Text.StringBuilder.ToString(startIndex: int, length: int) : string
Raw view Test code New version

More information

Link:http://fssnip.net/eb
Posted:12 years ago
Author:Kit Eason
Tags: testing; math;

This web site is created using F# and Suave web server. It is hosted on Azure and the source code is on GitHub. Contributions are welcome!

The first version of fssnip.net has been created by @tomaspetricek back in 2010. This web site is a new, open-source and contribution-friendly version.