python - 生成拉丁方的有效方法(或在两个轴上唯一地随机排列矩阵中的数字 - 使用 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

仅供引用，您正在寻找的是一种生成 latin squares 的方法.至于解决方案，就看你的“随机”程度是多少了。

我会设计至少四种主要技术，其中两种已经被提出。因此，我将简要描述其他两个:

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 的类似数独的回溯解决方案)。

对于 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!) 进行扩展) O(n)) 但不像解决方案 1 那样随机。解决方案 3 非常慢并且性能可能会有很大差异(可以通过计算而不是猜测最后一次迭代来加快速度)。

获得更多技术性，其他高效算法在以下内容中讨论:

• Jacobson, M. T. 和 Matthews, P. (1996)，生成均匀分布的随机拉丁方。 J. 结合。设计，4:405-437。 doi:10.1002/(SICI)1520-6610(1996)4:6<405::AID-JCD3>3.0.CO;2-J