大小为n的拉丁方阵是指各行列中的每个符号仅出现一次，随机拉丁方阵生成任意给定n个符号的随机输出。
以n=4为例生成随机拉丁方阵
0 2 3 1
2 1 0 3
3 0 1 2
1 3 2 0
任务
创建一个给定大小为n的生成随机拉丁方阵的函数（routine/procedure/method/… ），并使用该函数生成一个n=5的随机拉丁方阵。
代码实现
C
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
// low <= num < high
int randInt(int low, int high) {
return (rand() % (high - low)) + low;
}
// shuffle an array of n elements
void shuffle(int *const array, const int n) {
if (n > 1) {
int i;
for (i = 0; i < n - 1; i++) {
int j = randInt(i, n);
int t = array[i];
array[i] = array[j];
array[j] = t;
}
}
}
// print an n * n array
void printSquare(const int *const latin, const int n) {
int i, j;
for (i = 0; i < n; i++) {
printf("[");
for (j = 0; j < n; j++) {
if (j > 0) {
printf(", ");
}
printf("%d", latin[i * n + j]);
}
printf("]\n");
}
printf("\n");
}
void latinSquare(const int n) {
int *latin, *used;
int i, j, k;
if (n <= 0) {
printf("[]\n");
return;
}
// allocate
latin = (int *)malloc(n * n * sizeof(int));
if (!latin) {
printf("Failed to allocate memory.");
return;
}
// initialize
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
latin[i * n + j] = j;
}
}
// first row
shuffle(latin, n);
// middle row(s)
for (i = 1; i < n - 1; i++) {
bool shuffled = false;
while (!shuffled) {
shuffle(&latin[i * n], n);
for (k = 0; k < i; k++) {
for (j = 0; j < n; j++) {
if (latin[k * n + j] == latin[i * n + j]) {
goto shuffling;
}
}
}
shuffled = true;
shuffling: {}
}
}
//last row
used = (int *)malloc(n * sizeof(int));
for (j = 0; j < n; j++) {
memset(used, 0, n * sizeof(int));
for (i = 0; i < n - 1; i++) {
used[latin[i * n + j]] = 1;
}
for (k = 0; k < n; k++) {
if (used[k] == 0) {
latin[(n - 1) * n + j] = k;
break;
}
}
}
free(used);
// print the result
printSquare(latin, n);
free(latin);
}
int main() {
// initialze the random number generator
srand((unsigned int)time((time_t)0));
latinSquare(5);
latinSquare(5);
latinSquare(10);
return 0;
}
输出：
[1, 4, 3, 0, 2]
[3, 1, 0, 2, 4]
[2, 3, 4, 1, 0]
[4, 0, 2, 3, 1]
[0, 2, 1, 4, 3]
[0, 2, 4, 1, 3]
[1, 3, 0, 4, 2]
[4, 0, 3, 2, 1]
[3, 1, 2, 0, 4]
[2, 4, 1, 3, 0]
[6, 8, 2, 1, 4, 7, 3, 9, 5, 0]
[8, 7, 3, 2, 0, 1, 6, 5, 4, 9]
[1, 3, 5, 6, 7, 9, 4, 0, 2, 8]
[2, 5, 1, 9, 8, 0, 7, 4, 3, 6]
[4, 9, 8, 5, 6, 2, 0, 1, 7, 3]
[9, 6, 7, 8, 2, 4, 1, 3, 0, 5]
[7, 2, 9, 0, 3, 6, 5, 8, 1, 4]
[3, 1, 0, 4, 5, 8, 2, 6, 9, 7]
[5, 0, 4, 7, 9, 3, 8, 2, 6, 1]
[0, 4, 6, 3, 1, 5, 9, 7, 8, 2]
C++
#include <algorithm>
#include <chrono>
#include <iostream>
#include <random>
#include <vector>
template <typename T>
std::ostream &operator<<(std::ostream &os, const std::vector<T> &v) {
auto it = v.cbegin();
auto end = v.cend();
os << '[';
if (it != end) {
os << *it;
it = std::next(it);
}
while (it != end) {
os << ", ";
os << *it;
it = std::next(it);
}
return os << ']';
}
void printSquare(const std::vector<std::vector<int>> &latin) {
for (auto &row : latin) {
std::cout << row << '\n';
}
std::cout << '\n';
}
void latinSquare(int n) {
if (n <= 0) {
std::cout << "[]\n";
return;
}
// obtain a time-based seed:
unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
auto g = std::default_random_engine(seed);
std::vector<std::vector<int>> latin;
for (int i = 0; i < n; ++i) {
std::vector<int> inner;
for (int j = 0; j < n; ++j) {
inner.push_back(j);
}
latin.push_back(inner);
}
// first row
std::shuffle(latin[0].begin(), latin[0].end(), g);
// middle row(s)
for (int i = 1; i < n - 1; ++i) {
bool shuffled = false;
while (!shuffled) {
std::shuffle(latin[i].begin(), latin[i].end(), g);
for (int k = 0; k < i; ++k) {
for (int j = 0; j < n; ++j) {
if (latin[k][j] == latin[i][j]) {
goto shuffling;
}
}
}
shuffled = true;
shuffling: {}
}
}
// last row
for (int j = 0; j < n; ++j) {
std::vector<bool> used(n, false);
for (int i = 0; i < n - 1; ++i) {
used[latin[i][j]] = true;
}
for (int k = 0; k < n; ++k) {
if (!used[k]) {
latin[n - 1][j] = k;
break;
}
}
}
printSquare(latin);
}
int main() {
latinSquare(5);
latinSquare(5);
latinSquare(10);
return 0;
}
输出：
[4, 3, 1, 2, 0]
[1, 0, 3, 4, 2]
[3, 2, 0, 1, 4]
[2, 1, 4, 0, 3]
[0, 4, 2, 3, 1]
[2, 4, 0, 3, 1]
[0, 3, 4, 1, 2]
[3, 0, 1, 2, 4]
[1, 2, 3, 4, 0]
[4, 1, 2, 0, 3]
[9, 3, 5, 0, 8, 2, 7, 1, 6, 4]
[0, 9, 4, 6, 1, 8, 5, 3, 7, 2]
[4, 1, 9, 7, 3, 5, 2, 0, 8, 6]
[2, 6, 8, 3, 4, 0, 9, 7, 1, 5]
[6, 5, 3, 4, 7, 9, 1, 8, 2, 0]
[1, 8, 6, 5, 2, 4, 0, 9, 3, 7]
[7, 2, 0, 8, 9, 1, 4, 6, 5, 3]
[3, 0, 7, 1, 5, 6, 8, 2, 4, 9]
[8, 4, 2, 9, 6, 7, 3, 5, 0, 1]
[5, 7, 1, 2, 0, 3, 6, 4, 9, 8]
Go
Restarting Row method
As the task is not asking for large squares to be generated and even n = 10 is virtually instant, we use a simple brute force approach here known as the ‘Restarting Row’ method (see Talk page). However, whilst easy to understand, this method does not produce uniformly random squares.
package main
import (
"fmt"
"math/rand"
"time"
)
type matrix [][]int
func shuffle(row []int, n int) {
rand.Shuffle(n, func(i, j int) {
row[i], row[j] = row[j], row[i]
})
}
func latinSquare(n int) {
if n <= 0 {
fmt.Println("[]\n")
return
}
latin := make(matrix, n)
for i := 0; i < n; i++ {
latin[i] = make([]int, n)
if i == n-1 {
break
}
for j := 0; j < n; j++ {
latin[i][j] = j
}
}
// first row
shuffle(latin[0], n)
// middle row(s)
for i := 1; i < n-1; i++ {
shuffled := false
shuffling:
for !shuffled {
shuffle(latin[i], n)
for k := 0; k < i; k++ {
for j := 0; j < n; j++ {
if latin[k][j] == latin[i][j] {
continue shuffling
}
}
}
shuffled = true
}
}
// last row
for j := 0; j < n; j++ {
used := make([]bool, n)
for i := 0; i < n-1; i++ {
used[latin[i][j]] = true
}
for k := 0; k < n; k++ {
if !used[k] {
latin[n-1][j] = k
break
}
}
}
printSquare(latin, n)
}
func printSquare(latin matrix, n int) {
for i := 0; i < n; i++ {
fmt.Println(latin[i])
}
fmt.Println()
}
func main() {
rand.Seed(time.Now().UnixNano())
latinSquare(5)
latinSquare(5)
latinSquare(10) // for good measure
}
输出
[3 2 1 0 4]
[0 3 2 4 1]
[4 1 0 3 2]
[2 4 3 1 0]
[1 0 4 2 3]
[3 1 0 4 2]
[1 0 2 3 4]
[2 4 3 0 1]
[4 3 1 2 0]
[0 2 4 1 3]
[9 2 8 4 6 1 7 5 0 3]
[4 3 7 6 0 8 5 9 2 1]
[2 1 9 7 3 4 6 0 5 8]
[8 6 0 5 7 2 3 1 9 4]
[5 0 6 8 1 3 9 2 4 7]
[7 5 4 9 2 0 1 3 8 6]
[3 9 2 1 5 6 8 4 7 0]
[1 4 5 2 8 7 0 6 3 9]
[6 8 3 0 4 9 2 7 1 5]
[0 7 1 3 9 5 4 8 6 2]
Latin Squares in Reduced Form method
Unlike the “Restarting Row” method, this method does produce uniformly random Latin squares for n <= 6 (see Talk page) but is more involved and therefore slower. It reuses some (suitably adjusted) code from the Latin Squares in Reduced Form and Permutations tasks.
package main
import (
"fmt"
"math/rand"
"sort"
"time"
)
type matrix [][]int
// generate derangements of first n numbers, with 'start' in first place.
func dList(n, start int) (r matrix) {
start-- // use 0 basing
a := make([]int, n)
for i := range a {
a[i] = i
}
a[0], a[start] = start, a[0]
sort.Ints(a[1:])
first := a[1]
// recursive closure permutes a[1:]
var recurse func(last int)
recurse = func(last int) {
if last == first {
// bottom of recursion. you get here once for each permutation.
// test if permutation is deranged.
for j, v := range a[1:] { // j starts from 0, not 1
if j+1 == v {
return // no, ignore it
}
}
// yes, save a copy
b := make([]int, n)
copy(b, a)
for i := range b {
b[i]++ // change back to 1 basing
}
r = append(r, b)
return
}
for i := last; i >= 1; i-- {
a[i], a[last] = a[last], a[i]
recurse(last - 1)
a[i], a[last] = a[last], a[i]
}
}
recurse(n - 1)
return
}
func reducedLatinSquares(n int) []matrix {
var rls []matrix
if n < 0 {
n = 0
}
rlatin := make(matrix, n)
for i := 0; i < n; i++ {
rlatin[i] = make([]int, n)
}
if n <= 1 {
return append(rls, rlatin)
}
// first row
for j := 0; j < n; j++ {
rlatin[0][j] = j + 1
}
// recursive closure to compute reduced latin squares
var recurse func(i int)
recurse = func(i int) {
rows := dList(n, i) // get derangements of first n numbers, with 'i' first.
outer:
for r := 0; r < len(rows); r++ {
copy(rlatin[i-1], rows[r])
for k := 0; k < i-1; k++ {
for j := 1; j < n; j++ {
if rlatin[k][j] == rlatin[i-1][j] {
if r < len(rows)-1 {
continue outer
} else if i > 2 {
return
}
}
}
}
if i < n {
recurse(i + 1)
} else {
rl := copyMatrix(rlatin)
rls = append(rls, rl)
}
}
return
}
// remaining rows
recurse(2)
return rls
}
func copyMatrix(m matrix) matrix {
le := len(m)
cpy := make(matrix, le)
for i := 0; i < le; i++ {
cpy[i] = make([]int, le)
copy(cpy[i], m[i])
}
return cpy
}
func printSquare(latin matrix, n int) {
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
fmt.Printf("%d ", latin[i][j]-1)
}
fmt.Println()
}
fmt.Println()
}
func factorial(n uint64) uint64 {
if n == 0 {
return 1
}
prod := uint64(1)
for i := uint64(2); i <= n; i++ {
prod *= i
}
return prod
}
// generate permutations of first n numbers, starting from 0.
func pList(n int) matrix {
fact := factorial(uint64(n))
perms := make(matrix, fact)
a := make([]int, n)
for i := 0; i < n; i++ {
a[i] = i
}
t := make([]int, n)
copy(t, a)
perms[0] = t
n--
var i, j int
for c := uint64(1); c < fact; c++ {
i = n - 1
j = n
for a[i] > a[i+1] {
i--
}
for a[j] < a[i] {
j--
}
a[i], a[j] = a[j], a[i]
j = n
i++
for i < j {
a[i], a[j] = a[j], a[i]
i++
j--
}
t := make([]int, n+1)
copy(t, a)
perms[c] = t
}
return perms
}
func generateLatinSquares(n, tests, echo int) {
rls := reducedLatinSquares(n)
perms := pList(n)
perms2 := pList(n - 1)
for test := 0; test < tests; test++ {
rn := rand.Intn(len(rls))
rl := rls[rn] // select reduced random square at random
rn = rand.Intn(len(perms))
rp := perms[rn] // select a random permuation of 'rl's columns
// permute columns
t := make(matrix, n)
for i := 0; i < n; i++ {
t[i] = make([]int, n)
}
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
t[i][j] = rl[i][rp[j]]
}
}
rn = rand.Intn(len(perms2))
rp = perms2[rn] // select a random permutation of 't's rows 2 to n
// permute rows 2 to n
u := make(matrix, n)
for i := 0; i < n; i++ {
u[i] = make([]int, n)
}
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
if i == 0 {
u[i][j] = t[i][j]
} else {
u[i][j] = t[rp[i-1]+1][j]
}
}
}
if test < echo {
printSquare(u, n)
}
if n == 4 {
for i := 0; i < 4; i++ {
for j := 0; j < 4; j++ {
u[i][j]--
}
}
for i := 0; i < 4; i++ {
copy(a[4*i:], u[i])
}
for i := 0; i < 4; i++ {
if testSquares[i] == a {
counts[i]++
break
}
}
}
}
}
var testSquares = [4][16]int{
{0, 1, 2, 3, 1, 0, 3, 2, 2, 3, 0, 1, 3, 2, 1, 0},
{0, 1, 2, 3, 1, 0, 3, 2, 2, 3, 1, 0, 3, 2, 0, 1},
{0, 1, 2, 3, 1, 2, 3, 0, 2, 3, 0, 1, 3, 0, 1, 2},
{0, 1, 2, 3, 1, 3, 0, 2, 2, 0, 3, 1, 3, 2, 1, 0},
}
var (
counts [4]int
a [16]int
)
func main() {
rand.Seed(time.Now().UnixNano())
fmt.Println("Two randomly generated latin squares of order 5 are:\n")
generateLatinSquares(5, 2, 2)
fmt.Println("Out of 1,000,000 randomly generated latin squares of order 4, ")
fmt.Println("of which there are 576 instances ( => expected 1736 per instance),")
fmt.Println("the following squares occurred the number of times shown:\n")
generateLatinSquares(4, 1e6, 0)
for i := 0; i < 4; i++ {
fmt.Println(testSquares[i][:], ":", counts[i])
}
fmt.Println("\nA randomly generated latin square of order 6 is:\n")
generateLatinSquares(6, 1, 1)
}
输出：
Two randomly generated latin squares of order 5 are:
2 1 3 4 0
4 3 0 1 2
1 0 2 3 4
0 4 1 2 3
3 2 4 0 1
1 2 3 4 0
0 3 4 2 1
2 4 0 1 3
4 0 1 3 2
3 1 2 0 4
Out of 1,000,000 randomly generated latin squares of order 4,
of which there are 576 instances ( => expected 1736 per instance),
the following squares occurred the number of times shown:
[0 1 2 3 1 0 3 2 2 3 0 1 3 2 1 0] : 1737
[0 1 2 3 1 0 3 2 2 3 1 0 3 2 0 1] : 1736
[0 1 2 3 1 2 3 0 2 3 0 1 3 0 1 2] : 1726
[0 1 2 3 1 3 0 2 2 0 3 1 3 2 1 0] : 1799
A randomly generated latin square of order 6 is:
3 5 1 0 4 2
2 0 5 4 1 3
0 4 2 5 3 1
1 3 4 2 0 5
5 1 0 3 2 4
4 2 3 1 5 0
Java
import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.Objects;
public class RandomLatinSquares {
private static void printSquare(List<List<Integer>> latin) {
for (List<Integer> row : latin) {
Iterator<Integer> it = row.iterator();
System.out.print("[");
if (it.hasNext()) {
Integer col = it.next();
System.out.print(col);
}
while (it.hasNext()) {
Integer col = it.next();
System.out.print(", ");
System.out.print(col);
}
System.out.println("]");
}
System.out.println();
}
private static void latinSquare(int n) {
if (n <= 0) {
System.out.println("[]");
return;
}
List<List<Integer>> latin = new ArrayList<>(n);
for (int i = 0; i < n; ++i) {
List<Integer> inner = new ArrayList<>(n);
for (int j = 0; j < n; ++j) {
inner.add(j);
}
latin.add(inner);
}
// first row
Collections.shuffle(latin.get(0));
// middle row(s)
for (int i = 1; i < n - 1; ++i) {
boolean shuffled = false;
shuffling:
while (!shuffled) {
Collections.shuffle(latin.get(i));
for (int k = 0; k < i; ++k) {
for (int j = 0; j < n; ++j) {
if (Objects.equals(latin.get(k).get(j), latin.get(i).get(j))) {
continue shuffling;
}
}
}
shuffled = true;
}
}
// last row
for (int j = 0; j < n; ++j) {
List<Boolean> used = new ArrayList<>(n);
for (int i = 0; i < n; ++i) {
used.add(false);
}
for (int i = 0; i < n - 1; ++i) {
used.set(latin.get(i).get(j), true);
}
for (int k = 0; k < n; ++k) {
if (!used.get(k)) {
latin.get(n - 1).set(j, k);
break;
}
}
}
printSquare(latin);
}
public static void main(String[] args) {
latinSquare(5);
latinSquare(5);
latinSquare(10);
}
}
输出：
[1, 3, 4, 0, 2]
[4, 0, 2, 1, 3]
[0, 2, 1, 3, 4]
[2, 1, 3, 4, 0]
[3, 4, 0, 2, 1]
[4, 2, 1, 3, 0]
[2, 1, 3, 0, 4]
[0, 3, 2, 4, 1]
[3, 4, 0, 1, 2]
[1, 0, 4, 2, 3]
[8, 7, 9, 0, 1, 2, 6, 5, 4, 3]
[4, 6, 3, 8, 0, 5, 2, 9, 1, 7]
[2, 1, 0, 4, 8, 9, 7, 3, 5, 6]
[6, 4, 8, 1, 9, 7, 3, 0, 2, 5]
[7, 9, 2, 6, 5, 3, 4, 8, 0, 1]
[9, 5, 1, 3, 2, 6, 8, 4, 7, 0]
[5, 0, 4, 9, 6, 8, 1, 7, 3, 2]
[3, 8, 5, 2, 7, 1, 0, 6, 9, 4]
[1, 3, 6, 7, 4, 0, 5, 2, 8, 9]
[0, 2, 7, 5, 3, 4, 9, 1, 6, 8]
Kotin
typealias matrix = MutableList<MutableList<Int>>
fun printSquare(latin: matrix) {
for (row in latin) {
println(row)
}
println()
}
fun latinSquare(n: Int) {
if (n <= 0) {
println("[]")
return
}
val latin = MutableList(n) { MutableList(n) { it } }
// first row
latin[0].shuffle()
// middle row(s)
for (i in 1 until n - 1) {
var shuffled = false
shuffling@
while (!shuffled) {
latin[i].shuffle()
for (k in 0 until i) {
for (j in 0 until n) {
if (latin[k][j] == latin[i][j]) {
continue@shuffling
}
}
}
shuffled = true
}
}
// last row
for (j in 0 until n) {
val used = MutableList(n) { false }
for (i in 0 until n - 1) {
used[latin[i][j]] = true
}
for (k in 0 until n) {
if (!used[k]) {
latin[n - 1][j] = k
break
}
}
}
printSquare(latin)
}
fun main() {
latinSquare(5)
latinSquare(5)
latinSquare(10) // for good measure
}
输出：
[4, 1, 2, 3, 0]
[1, 3, 0, 2, 4]
[3, 2, 4, 0, 1]
[0, 4, 3, 1, 2]
[2, 0, 1, 4, 3]
[2, 0, 3, 1, 4]
[0, 4, 1, 3, 2]
[1, 3, 2, 4, 0]
[3, 2, 4, 0, 1]
[4, 1, 0, 2, 3]
[7, 8, 4, 6, 5, 2, 9, 3, 1, 0]
[1, 5, 8, 2, 3, 0, 7, 9, 4, 6]
[6, 9, 5, 8, 7, 1, 3, 4, 0, 2]
[0, 6, 9, 4, 8, 3, 1, 2, 7, 5]
[4, 1, 3, 0, 6, 5, 8, 7, 2, 9]
[5, 0, 1, 7, 9, 4, 2, 6, 3, 8]
[2, 3, 6, 9, 4, 7, 0, 8, 5, 1]
[3, 7, 2, 5, 0, 9, 6, 1, 8, 4]
[8, 2, 0, 3, 1, 6, 4, 5, 9, 7]
[9, 4, 7, 1, 2, 8, 5, 0, 6, 3]
