5

N 次元のグリッドと、座標 (x1、x2、...、xN) を持つ点 X があるとします。簡単にするために、グリッドは無制限であると仮定できます。

半径 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

中心から再帰的に作業し、ゼロ距離を1回カウントして、対称性に取り組むことができます。このPython実装は、低次元の「ステム」ベクトルで機能し、一度に1つの1次元スライスを実現します。逆のこともできますが、それは部分的な超球を反復することを意味します。数学的には同じですが、両方のアプローチの効率は言語に大きく依存します。

ターゲットスペースのカーディナリティを事前に知っている場合は、反復的な実装を作成することをお勧めします。

以下は、私のラップトップで約200ミリ秒の6次元の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

  • カーディナリティ≤DのRのすべての整数分割を生成します
  • パーティションごとに、繰り返しなしで並べ替えます
  • 順列ごとに、すべての記号をいじります

たとえば、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

radius = 4、dimension = 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 に答える