生成拉丁方块的有效方法(或在两个轴上唯一地在矩阵中随机置换数字 - 使用NumPy)

Question

例如,如果有5个数字1,2,3,4,5

我想要一个随机的结果

[[ 2, 3, 1, 4, 5]
 [ 5, 1, 2, 3, 4]
 [ 3, 2, 4, 5, 1]
 [ 1, 4, 5, 2, 3]
 [ 4, 5, 3, 1, 2]]

确保其行和列中的每个数字都是唯一的.

有没有一种有效的方法来做到这一点？

我尝试使用while循环为每次迭代生成一行,但似乎效率不高.

import numpy as np

numbers = list(range(1,6))
result = np.zeros((5,5), dtype='int32')
row_index = 0
while row_index < 5:
    np.random.shuffle(numbers)
    for column_index, number in enumerate(numbers):
       if number in result[:, column_index]:
           break
       else:
           result[row_index, :] = numbers
           row_index += 1

Answer 1

仅作为参考，您正在寻找的是一种生成拉丁方的方法。至于解决方案，则取决于您要使用多少随机“随机数”。

我将设计至少四个主要技术，其中两个已经提出。因此，我将简要描述另外两个：

1. 遍历项目的所有可能排列，并接受满足行中唯一性约束的第一个
2. 仅使用循环排列来构建后续行：这些是通过构造来满足沿行的唯一性约束的（循环转换可以向前或向后进行）；为了改善“随机性”，可以对行进行混洗

假设我们使用标准的Python数据类型，因为我看不到使用NumPy的真正好处（但是np.ndarray如果需要，可以很容易地将结果转换为），这将在代码中进行（第一个功能只是检查解决方案是否正确） ）：

import random
import math
import itertools

# this only works for Iterable[Iterable]
def is_latin_rectangle(rows):
    valid = True
    for row in rows:
        if len(set(row)) < len(row):
            valid = False
    if valid and rows:
        for i, val in enumerate(rows[0]):
            col = [row[i] for row in rows]
            if len(set(col)) < len(col):
                valid = False
                break
    return valid

def is_latin_square(rows):
    return is_latin_rectangle(rows) and len(rows) == len(rows[0])

# : prepare the input
n = 9
items = list(range(1, n + 1))
# shuffle items
random.shuffle(items)
# number of permutations
print(math.factorial(n))


def latin_square1(items, shuffle=True):
    result = []
    for elems in itertools.permutations(items):
        valid = True
        for i, elem in enumerate(elems):
            orthogonals = [x[i] for x in result] + [elem]
            if len(set(orthogonals)) < len(orthogonals):
                valid = False
                break
        if valid:
            result.append(elems)
    if shuffle:
        random.shuffle(result)
    return result

rows1 = latin_square1(items)
for row in rows1:
    print(row)
print(is_latin_square(rows1))


def latin_square2(items, shuffle=True, forward=False):
    sign = -1 if forward else 1
    result = [items[sign * i:] + items[:sign * i] for i in range(len(items))]
    if shuffle:
        random.shuffle(result)
    return result

rows2 = latin_square2(items)
for row in rows2:
    print(row)
print(is_latin_square(rows2))

rows2b = latin_square2(items, False)
for row in rows2b:
    print(row)
print(is_latin_square(rows2b))

为了进行比较，还介绍了一种尝试随机排列并接受有效排列的实现方式（从根本上讲，@ hpaulj提出了什么）。

def latin_square3(items):
    result = [list(items)]
    while len(result) < len(items):
        new_row = list(items)
        random.shuffle(new_row)
        result.append(new_row)
        if not is_latin_rectangle(result):
            result = result[:-1]
    return result

rows3 = latin_square3(items)
for row in rows3:
    print(row)
print(is_latin_square(rows3))

我还没有时间实现其他方法（使用@ConfusedByCode的类似Sudoku的解决方案）。

有以下时间安排n = 5：

%timeit latin_square1(items)
321 µs ± 24.7 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

%timeit latin_square2(items)
7.5 µs ± 222 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

%timeit latin_square2(items, False)
2.21 µs ± 69.9 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

%timeit latin_square3(items)
2.15 ms ± 102 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

...并针对n = 9：

%timeit latin_square1(items)
895 ms ± 18.1 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

%timeit latin_square2(items)
12.5 µs ± 200 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

%timeit latin_square2(items, False)
3.55 µs ± 55.5 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

%timeit latin_square3(items)
The slowest run took 36.54 times longer than the fastest. This could mean that an intermediate result is being cached.
9.76 s ± 9.23 s per loop (mean ± std. dev. of 7 runs, 1 loop each)

因此，解决方案1具有相当大的随机性，但并不是非常快（用缩放O(n!)），解决方案2（和2b）要快得多（用缩放O(n)），但不如解决方案1随机。性能可能会发生很大的变化（可以通过计算而不是猜测最后的迭代来加快速度）。

有关获得更多技术和其他有效算法的信息，请参见：

• Jacobson，MT和Matthews，P.（1996），生成均匀分布的随机拉丁方。J.康宾。设计，4：405-437。doi：10.1002 /（SICI）1520-6610（1996）4：6 <405 :: AID-JCD3> 3.0.CO; 2-J

Answer 2

编辑：下面是norok2答案中第二个解决方案的实现。

编辑：我们可以再次打乱生成的方块，使其真正随机。因此求解函数可以修改为：

def solve(numbers):
    shuffle(numbers)
    shift = randint(1, len(numbers)-1)
    res = []

    for r in xrange(len(numbers)):
        res.append(list(numbers))
        numbers = list(numbers[shift:] + numbers[0:shift])

    rows = range(len(numbers))
    shuffle(rows)

    shuffled_res = []
    for i in xrange(len(rows)):
        shuffled_res.append(res[rows[i]])

    return shuffled_res

编辑：我之前误解了这个问题。因此，这是一种“快速”方法，可以生成“某种程度上”的随机解决方案。基本思想是，

    a, b, c
    b, c, a
    c, a, b

我们可以将一行数据移动固定的步长来形成下一行。这将符合我们的限制。

所以，这是代码：

from random import shuffle, randint


def solve(numbers):
    shuffle(numbers)
    shift = randint(1, len(numbers)-1)
    res = []

    for r in xrange(len(numbers)):
        res.append(list(numbers))
        numbers = list(numbers[shift:] + numbers[0:shift])

    return res


def check(arr):
    for c in xrange(len(arr)):
        col = [arr[r][c] for r in xrange(len(arr))]
        if len(set(col)) != len(col):
            return False
    return True


if __name__ == '__main__':
    from pprint import pprint
    res = solve(range(5))
    pprint(res)
    print check(res)

如果您不坚持使用我不熟悉的 numpy，这是 itertools 的一个可能的解决方案：

import itertools
from random import randint
list(itertools.permutations(range(1, 6)))[randint(0, len(range(1, 6))]

# itertools returns a iterator of all possible permutations of the given list.