相關歷史
據說普魯士的腓特列大帝曾組成一支儀仗隊,儀仗隊共有36名軍官,來自6支部隊,每支部隊中,上校、中校、少校、上尉、中尉、少尉各一名。他希望這36名軍官排成6×6的方陣,方陣的每一行,每一列的6名軍官來自不同的部隊並且軍銜各不相同。令他惱火的是,無論怎么絞盡腦汁也排不成。
後來,他去求教瑞士著名的大數學家歐拉。歐拉發現這是一個不可能完成的任務。
來自n個部隊的n種軍銜的n×n名軍官,如果能排成一個正方形,每一行,每一列的n名軍官來自不同的部隊並且軍銜各不相同,那么就稱這個方陣叫正交拉丁方陣。歐拉猜測在
n=2,6,10,14,18,…
時,正交拉丁方陣不存在。然而到了上世紀60年代,人們用計算機造出了n=10的正交拉丁方陣,推翻了歐拉的猜測。現在已經知道,除了n=2,6以外,其餘的正交拉丁方陣都存在,而且有多種構造的方法。
標準型
當一個拉丁方陣的第一行與第一列的元素按
順序排列時,此為這個拉丁方陣的標準型,英語稱為"reduced Latin square, normalized Latin square, 或Latin square in standard form"。
同型類別
許多對於拉丁方陣的運算都會產生新的拉丁方陣。例如說,交換拉丁方陣里的行、交換拉丁方陣里的列、或是交換拉丁方陣里的元素的符號,都會得到一個新的拉丁方陣。交換拉丁方陣里的行、交換拉丁方陣里的列、或是交換拉丁方陣里的元素的符號所得的新的拉丁方陣與原來的拉丁方陣稱為同型(isotopic)。同型(isotopism)是一個
等價關係,因此所有的拉丁方陣所成的
集合可以分成同型類別(isotopic class)的子集合,同型的拉丁方陣屬於同一個同型類別,而不屬於同一個同型類別的拉丁方陣則不同型。
正交拉丁方陣
定義
設有兩個
階數相同(為)的拉丁方陣
,其中將所有放置位置相同的元素組合成一個元組,組合成一個新的矩陣
。 當這個新的矩陣
中每一個元素互不相同時,拉丁方陣
和
是互相正交的。 此時,
和
即為一對
正交拉丁方。 而在階數固定的情況下,所有兩兩正交的拉丁方所成的集合稱為
正交拉丁方族。
構造
請你造一個n=4的正交拉丁方陣。
![拉丁方陣 拉丁方陣](/img/c/588/cGcq5CZhFmM5Q2Y3YGZihDOhRTMmFmMidzNhRzLtVGdp9yYpB3LltWahJ2Lt92YuUHZpFmYuMmczdWbp9yL6MHc0RHa.jpg)
如果你有撲克牌,請用四種花色(梅花,方塊,紅心,黑桃)的1(即A)、2、3、4共16張牌,將它們排成4×4的方陣,每一行,每一列四種花色俱全,並且都有1、2、3、4。
特點
仔細欣賞一下,除了每行每列都有1、2、3、4,而且花色齊全。另外,這個圖還有許多特點:
1. 一條對角線(從左上到右下)上全是4,另一條對角線(從右上到左下)上全是A。
2. 方塊與梅花是左右對稱的,紅桃與黑桃也是左右對稱的。就是說,如果沿中間的豎線將圖對摺,方塊與梅花相合,紅桃與黑桃相合。
3. 方塊與黑桃,梅花與紅桃上下對稱。就是說,如果沿中間的橫線將圖對摺,方塊和黑桃相合,梅花與紅桃相合。
4. A與4,2與3左右對稱。
5. 兩條對角線上四種四種花色齊全。
6. 方塊與紅桃中心對稱,黑桃與梅花中心對稱,就是說,如果將圖形繞中心(圖中橫線與豎線的點)旋轉180°,左上的方塊與右下的紅桃相合。
上圖是另一種4階(n=4)的正交拉丁方陣,請同學們自己欣賞,發現一些規律和特點。
學習數學,應當注意欣賞數學的美:整齊、對稱、有規律、簡單、自然…會欣賞數學的美才能將數學學的更好;學好了數學,也就提高了對數學美的認識。
正交拉丁方
定理
套用
當該定理中的等號成立時,則該階正交拉丁方族被稱為完全的。 可以分析得到,當n為1時,只存在一個拉丁方,當n為2時,不存在正交拉丁方族。 此外,當n為6時,也不存在正交拉丁方族,這個結論是通過對三十六軍官問題的嘗試得到的。 三十六軍官問題指的是是否有一個解決方案使得來自6個不同地區的6個不同軍銜的軍官排成
的方陣,其中每一行每一列的軍官都來自於不同的地區且具有不同的軍銜。 而該問題的方案即為6階正交拉丁方的個數,該問題於1901年被Gaston Tarry證明為無解。 除了上述三種情況外,當階數小於等於8時,均存在有n-1個正交的拉丁方。
如當n=3時,存在兩個正交的拉丁方。
當
階數更多時
,可以通過正交拉丁方表得到正交拉丁方族。
判斷拉丁方陣
拉丁方陣是一種n×n的方陣,方陣中恰有n種不同的元素,每種元素恰有n個,並且每種元素在一行和一列中 恰好出現一次。著名數學家和物理學家歐拉使用拉丁字母來作為拉丁方陣里元素的符號,拉丁方陣因此而得名。例如下式是一個3×3的拉丁方陣:
如果一個拉丁方陣的第一行和第一列按照元素的先後順序來排列,那么這稱為拉丁方陣的標準型,例如下式就是一個3x3的拉丁方陣標準型,第一行和第一列都是”1 2 3”。
C語言
//t=0時,不是拉丁方陣
//t=1時,是拉丁方陣
//t=2時,是標準型拉丁方陣
#include<stdio.h>
#include<string.h>
int a[101][101],b[101][101],c[101][101];
#define clr(x) memset(x,0,sizeof(x))
int main()
{
int n,i,j,k,t;
while(scanf("%d",&n)&&n)
{
t=1;k=1;
clr(a);clr(b);clr(c);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
scanf("%d",&a[i][j]);
b[i][a[i][j]]++;
c[a[i][j]][j]++;
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
if(b[i][j]!=1||c[i][j]!=1)
{t=0;break;}
}
/*判斷是否是標準型*/
if(t){
for(i=1;i<=n;i++)
if(a[1][i]!=i||a[i][1]!=i)
{k=0;break;}
if(k)t=2;
}
printf("%d\n",t);
}
}
構造 NXN 階的拉丁方陣(2<=N<=9),使方陣中的每一行和每一列中數字1到N只出現一次。如N=4時:
1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3
*問題分析與算法設計
構造拉丁方陣的方法很多,這裡給出最簡單的一種方法。觀察給出的例子,可以發現:若將每 一行中第一列的數字和最後一列的數字連起來構成一個環,則該環正好是由1到N順序構成;對於第i行,這個環的開始數字為i。按照 此規律可以很容易的寫出程式。下面給出構造6階拉丁方陣的程式。
*程式說明與注釋
#include<stdio.h>
#define N 6 /*確定N值*/
int main()
{
int i,j,k,t;
printf("The possble Latin Squares of order %d are:\n",N);
for(j=0;j<N;j++) /*構造N個不同的拉丁方陣*/
{
for(i=0;i<N;i++)
{
t=(i+j)%N; /*確定該拉丁方陣第i 行的第一個元素的值*/
for(k=0;k<N;k++) /*按照環的形式輸出該行中的各個元素*/
printf("%d",(k+t)%N+1);
printf("\n");
}
printf("\n");
}
}
*運行結果
The possble Latin Squares of order 6 are:
1 2 3 4 5 6 2 3 4 5 6 1 3 4 5 6 1 2
2 3 4 5 6 1 3 4 5 6 1 2 4 5 6 1 2 3
3 4 5 6 1 2 4 5 6 1 2 3 5 6 1 2 3 4
4 5 6 1 2 3 5 6 1 2 3 4 6 1 2 3 4 5
5 6 1 2 3 4 6 1 2 3 4 5 1 2 3 4 5 6
6 1 2 3 4 5 1 2 3 4 5 6 2 3 4 5 6 1
4 5 6 1 2 3 5 6 1 2 3 4 6 1 2 3 4 5
5 6 1 2 3 4 6 1 2 3 4 5 1 2 3 4 5 6
6 1 2 3 4 5 1 2 3 4 5 6 2 3 4 5 6 1
1 2 3 4 5 6 2 3 4 5 6 1 3 4 5 6 1 2
2 3 4 5 6 1 3 4 5 6 1 2 4 5 6 1 2 3
3 4 5 6 1 2 4 5 6 1 2 3 5 6 1 2 3 4