算法生成多个拉丁方大小= {4,5，6 ...} [英] Algorithm to generate more Latin Squares size = {4, 5, 6 ... }

问题描述

INTRO

有关拉丁方的更多信息，你可以看看在维基百科的文章。或者这里（FOO的评论）。

在present算法是用Pascal写的，它是部分与其他算法翻译：的 $ C $通过窥镜℃。部分原因是因为前者递增，现在产生了更多的可能性。例如，

• 在所有尺寸的拉丁方= {1，2，3};
• 144 576大小= {4};
• 在2880的161280大小= {5};
• 77769的812851200大小= {6}等。

问题

有没有更好的方法来产生更多的可能性，一些随机的因素是什么？

好奇心

拉​​丁方可以用在心理学研究（激励控制），以确定刺激（标牌）位置（矩阵divised显示器上）不重复审判审判。广场上的每一行是一个试验，其中的刺激是psented就通过列符号$ P $。

code

 程序LatinSquares;

{$ APPTYPE CONSOLE}

用途
  SysUtils单元

变种
  混乱的，序列，旋转，体征：整数数组;
  方：整数数组的数组;
  I，J，K，大小：整数;

  程序SetArrayLength（A大小：整数）;
  开始
    SetLength（标志，A大小）; //需要ordenated
    SetLength（旋转，A大小）; //多少次左转
    SetLength（错杂，A大小）; //随机的原始状态
    SetLength（序列A大小）; //工作阵列被旋转并先复位
    SetLength（方形，A大小，A大小）; //拉丁广场
  结束;

  程序随机播放（VAR ARRAY1：整数数组; A大小：整数）;
  VAR V，aTemp，ARANDOM：整数;
  开始
    对于五：= 0至A大小 -  1做ARRAY1 [V]：= V + 1;

    对于五：= 0至A大小 -  1做
      开始
        ARANDOM：=圆形（随机*（A大小 -  1））;
        aTemp：= ARRAY1 [ARANDOM]
        ARRAY1 [ARANDOM]：= ARRAY1 [V]
        ARRAY1 [V]：= aTemp;
      结束;
  结束;

 //向左旋转
  程序旋转（VAR ARRAY2：整数数组; A大小，aTimes：整数）;
  变种aTemp，V，X：整数;
  开始
    为X：= 0至aTimes  -  1做
      开始
        aTemp：= ARRAY2 [0];
        对于五：=低（ARRAY2）到高（ARRAY2）做ARRAY2 [V]：= ARRAY2 [V + 1];
        ARRAY2 [A大小 -  1]：= aTemp;
      结束;
  结束;

开始
  随机化;
  大小：= 6; // Readln（大小）;
  SetArrayLength（大小）;

  洗牌（混乱，大小）;
  洗牌（旋转，大小）;

  //迹象阵列需要被ordenated分配拉丁广场
  对于i：= 0尺寸 -  1做招牌[我]：= I + 1;

  对于i：= 0尺寸 -  1做
    开始
      //重置/设置工作数组随机原始状态
      对于k：= 0尺寸 -  1做序列[K]：=混乱[K]
      //旋转工作阵列向左
      旋转（顺序，大小，旋转[I]）;
      //分配拉丁广场，
      对于j：= 0尺寸 -  1做多[J，序列[J]  -  1]：=迹象[I]
      //输出
    结束;
结束。
 

输出

  //大小：= 5;

00100
10000
01000
00001
00010

02100
10002
01020
00201
20010

02130
10302
31020
03201
20013

02134
10342
31420
43201
24013

52134
15342
31425
43251
24513
 

解决方案

雅各布森和P.马修斯似乎是一个更好的（但很难实现过）的方式。

  

微米。 T.雅各布森和P.马修斯，从而产生均匀分布   随机拉丁方，J组合设计4（1996年），405-437

INTRO

For more information about Latin Squares you could take a look at the Wikipédia article. Or here (foo's comment).

The present algorithm was written in pascal and it was partially translated from other algorithm: Code through the Looking Glass. Partially because the former was incremented and now generates more possibilities. For instance,

• all Latin squares on size = {1, 2, 3};
• 144 of 576 on size = {4} ;
• 2880 of 161280 on size = {5};
• 77769 of 812851200 on size = {6} and so on.

QUESTION

Is there a better approach to generate even more possibilities with some random factor?

Curiosity

Latin Squares can be used in psychological research (Stimulus control) to determine stimulus (signs) position (on a matrix divised monitor) without repetition trial to trial. Each row of the square is a trial where stimuli are presented regarding the sign through the columns.

CODE

program LatinSquares;

{$APPTYPE CONSOLE}

uses
  SysUtils

var
  jumbled, sequence, rotateS, signs: array of integer;
  square : array of array of integer;
  i, j, k, size: integer;

  procedure SetArrayLength (aSize : integer);
  begin
    SetLength(signs, aSize); //need to be ordenated
    SetLength(rotateS, aSize);//how many times to rotate left
    SetLength(jumbled, aSize);//a random original state
    SetLength(sequence, aSize);//work array to be rotated and to be reseted
    SetLength(square, aSize, aSize);//the latin square
  end;

  procedure Shuffle(var array1 : array of integer ; aSize : integer);
  var v, aTemp, aRandom : integer;
  begin
    for v := 0 to aSize - 1 do array1[v] := v + 1;

    for v := 0 to aSize - 1 do
      begin
        aRandom := Round(Random * (aSize - 1));
        aTemp := array1[aRandom];
        array1[aRandom] := array1[v];
        array1[v] := aTemp;
      end;
  end;

 //Rotate left 
  procedure Rotate(var array2 : array of integer; aSize, aTimes : integer); 
  var aTemp, v, x : integer;
  begin
    for x := 0 to aTimes - 1 do
      begin
        aTemp := array2[0];
        for v := Low(array2) to High(array2) do array2[v] := array2[v + 1];
        array2[aSize - 1] := aTemp;
      end;
  end;

begin
  Randomize;
  Size := 6; //Readln(Size);
  SetArrayLength(Size);

  shuffle(jumbled, size); 
  shuffle(rotateS, size);

  //signs array need to be ordenated to assign the latin square
  for i := 0 to size - 1 do signs[i] := i + 1; 

  for i := 0 to size - 1 do
    begin
      //reset/set the work array to a random original state
      for k := 0 to size - 1 do sequence[k] := jumbled[k];
      //rotate the work array to the left  
      rotate(sequence, size, rotateS[i]); 
      //assign the latin square,        
      for j := 0 to size - 1 do square[j, sequence[j] - 1] := signs[i];
      //OUTPUT 
    end;
end.

OUTPUT

//size := 5;

00100
10000
01000
00001
00010

02100
10002
01020
00201
20010

02130
10302
31020
03201
20013

02134
10342
31420
43201
24013

52134
15342
31425
43251
24513

解决方案

Jacobson and P. Matthews seems to be a better (but harder to implement too) approach.

M. T. Jacobson and P. Matthews, Generating uniformly distributed random Latin squares, J. Combinatorial Design 4 (1996), 405-437

这篇关于算法生成多个拉丁方大小= {4,5，6 ...}的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！