5

比如说，我们有一个 N 维网格和其中的某个点 X，坐标为 (x1, x2, ..., xN)。为简单起见，我们可以假设网格是无界的。

假设有一个半径 R 和一个以 X 为中心的半径的球体，即网格中所有点的集合，使得它们到 X 的曼哈顿距离等于 R。

我怀疑他们将是 2*N*R 这样的点。

我的问题是：我如何以有效和简单的方式枚举它们？“枚举”是指算法，在给定 N、X 和 R 的情况下，该算法将生成形成该球体的点列表（其中点是它的坐标列表）。

更新：最初我错误地将我使用的度量标准称为“汉明距离”。我向所有回答问题的人道歉。感谢 Steve Jessop 指出这一点。

4

3 回答 3

4

考虑限制超球面的最小轴对齐超立方体，并编写一个程序来枚举超立方体内的网格点。

然后，您只需要一个简单的过滤器功能，它可以让您丢弃立方体上而不是超球面中的点。

对于小尺寸，这是一种简单而有效的解决方案。例如，对于 2D，为边界正方形枚举的点中有 20% 被丢弃；对于 6D，几乎 90% 的超立方体点被丢弃。

对于更高的维度，您将不得不使用更复杂的方法：遍历每个维度（如果维度的数量是可变的，您可能需要使用递归函数）。对于每个循环，您必须根据已计算的网格组件的值调整最小值和最大值。好吧，尝试为 2D 做它，枚举一个圆的点，一旦你理解了它，将这个过程推广到更高的维度将非常简单。

更新：呃，等一下，你想使用曼哈顿距离。将交叉多面体称为“球体”可能是正确的，但我发现它很混乱！在任何情况下，您都可以使用相同的方法。

如果您只想枚举交叉多面体的超曲面上的点，那么解决方案也非常相似，您必须以适当的限制遍历每个维度。例如：

for (i = 0; i <= n; i++)
  for (j = 0; j + i <= n; j++)
    ...
       for (l = 0; l + ...+ j + i <= n; l++) {
         m = n - l - ... - j - i;
         printf(pat, i, j, ..., l, m);
       }

对于以这种方式生成的每个点，您将不得不考虑否定任何组件所产生的所有变化以覆盖所有面，然后用向量 X 置换它们。

更新

X = 0 情况下的 Perl 实现：

#!/usr/bin/perl

use strict;
use warnings;

sub enumerate {
    my ($d, $r) = @_;

    if ($d == 1) {
        return ($r ? ([-$r], [$r]) : [0])
    }
    else {
        my @r;
        for my $i (0..$r) {
            for my $s (enumerate($d - 1, $r - $i)) {
                for my $j ($i ? (-$i, $i) : 0) {
                    push @r, [@$s, $j]
                }
            }
        }
        return @r;
    }
}

@ARGV == 2 or die "Usage:\n  $0 dimension radius\n\n";
my ($d, $r) = @ARGV;
my @r = enumerate($d, $r);
print "[", join(',', @$_), "]\n" for @r;
于 2012-06-22T22:07:09.827 回答
1

您可以从中心递归地工作，计算一次零距离并处理对称性。这个 Python 实现适用于低维“stem”向量，一次实现一个一维切片。也可以反过来做，但这意味着在部分超球面上进行迭代。虽然在数学上相同，但两种方法的效率在很大程度上取决于语言。

如果您事先知道目标空间的基数，我建议您编写一个迭代实现。

下面在我的笔记本电脑上以大约 200 毫秒的时间在六个维度上列举了一个 R=16 超级乐高积木上的点。当然，随着维度的增加或球体的增大，性能会迅速下降。

def lapp(lst, el):
    lst2 = list(lst)
    lst2.append(el)
    return lst2

def hypersphere(n, r, stem = [ ]):
    mystem  = lapp(stem, 0)
    if 1 == n:
            ret = [ mystem ]
            for d in range(1, r+1):
                    ret.append(lapp(stem,  d))
                    ret.append(lapp(stem, -d))
    else:
            ret     = hypersphere(n-1, r, mystem)
            for d in range(1, r+1):
                    mystem[-1] = d
                    ret.extend(hypersphere(n-1, r-d, mystem))
                    mystem[-1] = -d
                    ret.extend(hypersphere(n-1, r-d, mystem))
    return ret

（此实现假设超球面以原点为中心。之后平移所有点比携带中心坐标更容易）。

于 2012-06-23T14:13:31.593 回答
1

输入：半径 R，尺寸 D

  • 生成 R 的所有整数分区，其基数 ≤ D
  • 对于每个分区，将其排列而不重复
  • 对于每个排列，旋转所有的符号

例如，python中的代码：

from itertools import *

# we have to write this function ourselves because python doesn't have it...
def partitions(n, maxSize):
    if n==0:
        yield []
    else:
        for p in partitions(n-1, maxSize):
            if len(p)<maxSize:
                yield [1] + p
            if p and (len(p)<2 or p[1]>p[0]):
                yield [ p[0]+1 ] + p[1:]

# MAIN CODE    
def points(R, D):
    for part in partitions(R,D):             # e.g. 4->[3,1]
        part = part + [0]*(D-len(part))      # e.g. [3,1]->[3,1,0]    (padding)
        for perm in set(permutations(part)): # e.g. [1,3,0], [1,0,3], ...
            for point in product(*[          # e.g. [1,3,0], [-1,3,0], [1,-3,0], [-...
                  ([-x,x] if x!=0 else [0]) for x in perm
                ]):
                yield point

半径=4，尺寸=3的演示：

>>> result = list( points(4,3) )

>>> result
[(-1, -2, -1), (-1, -2, 1), (-1, 2, -1), (-1, 2, 1), (1, -2, -1), (1, -2, 1), (1, 2, -1), (1, 2, 1), (-2, -1, -1), (-2, -1, 1), (-2, 1, -1), (-2, 1, 1), (2, -1, -1), (2, -1, 1), (2, 1, -1), (2, 1, 1), (-1, -1, -2), (-1, -1, 2), (-1, 1, -2), (-1, 1, 2), (1, -1, -2), (1, -1, 2), (1, 1, -2), (1, 1, 2), (0, -2, -2), (0, -2, 2), (0, 2, -2), (0, 2, 2), (-2, 0, -2), (-2, 0, 2), (2, 0, -2), (2, 0, 2), (-2, -2, 0), (-2, 2, 0), (2, -2, 0), (2, 2, 0), (-1, 0, -3), (-1, 0, 3), (1, 0, -3), (1, 0, 3), (-3, -1, 0), (-3, 1, 0), (3, -1, 0), (3, 1, 0), (0, -1, -3), (0, -1, 3), (0, 1, -3), (0, 1, 3), (-1, -3, 0), (-1, 3, 0), (1, -3, 0), (1, 3, 0), (-3, 0, -1), (-3, 0, 1), (3, 0, -1), (3, 0, 1), (0, -3, -1), (0, -3, 1), (0, 3, -1), (0, 3, 1), (0, -4, 0), (0, 4, 0), (0, 0, -4), (0, 0, 4), (-4, 0, 0), (4, 0, 0)]

>>> len(result)
66

（上面我过去常常set(permutations(...))得到不重复的排列，这通常效率不高，但由于点的性质，这里可能无关紧要。如果效率很重要，你可以用你选择的语言编写自己的递归函数。）

这种方法是有效的，因为它不随超体积缩放，而只是随超曲面缩放，这就是您要枚举的内容（除了非常大的半径之外可能无关紧要：例如，将为您节省大约 100 倍的速度如果你的半径是 100）。

于 2012-06-26T00:34:45.213 回答