algorithm - (x * y) の降順で 2D 平面上のグリッド ポイントを列挙します。

Question

N > 0andが与えられた場合M > 0、(x * y) の降順で 1 <= x <= N および 1 <= y <= M となるすべての (x, y) ペアを列挙したいと思います。例: N = 3 および M = 2 の場合、列挙シーケンスは次のようになります。

1. (3, 2) -- 3 * 2 = 6
2. (2, 2) -- 2 * 2 = 4
3. (3, 1) -- 3 * 1 = 3
4. (2, 1) -- 2 * 1 = 2
5. (1, 2) -- 1 * 2 = 2
6. (1, 1) -- 1 * 1 = 1

との順序を(2, 1)入れ替える(1, 2)ことができます。明らかな方法の 1 つは、それらをすべてリストし、 に挿入して、独自の比較関数vector<pair<int, int> >で呼び出すことです。std::sort()ただし、N と M は大きくなる可能性があり、ほとんどの場合、数列の最初の数項だけが必要なので、すべてを並べ替えて生成するのではなく、そのような数列を生成するよりスマートな方法があることを願っています。N*M配列要素と同じ数が必要です。

更新:ほとんどの場合、必要なのは最初の数項だけですが、必要な項の数は列挙前には不明であることを忘れていました。

Answer 1

時間をほぼ同じに保ちながらスペースを節約したいだけの場合は、連続して小さい各要素が要素の1つに隣接している（2Dグリッド内で）必要があるという事実を頼りにできます。あなたはすでに遭遇しました。（これは誘導で証明できますが、特に難しいことではありません。残りの部分では、M> = Nと仮定します。）

基本的なアルゴリズムは次のようになります。

Start with a list (Enumerated Points) containing just the maximum element, M*N
Create a max heap (Candidates) containing (M-1),N and M,(N-1).
Repeat this:
    1.Pick the largest value (x,y) in Candidates and append it to Enumerated Points
    2.Add (x-1),y and x,(y-1) to Candidates if they are not there already

列挙ポイントにさらに要素が必要な限り、これを繰り返すことができます。候補の最大サイズはM+Nである必要があるため、これはO（k log（M + N））であると思います。ここで、kは必要なポイント数です。

補遺：重複を避けることは完全に難しいことではありませんが、言及する価値があります。このアルゴリズムでは、グリッドをレイアウトして、右下に移動すると数値が下がると仮定します。とにかく、それはこのようになります：

アルゴリズムの開始時に、列ごとに1つの要素を持つ配列（列サイズ）を作成します。この配列に、列挙されたポイントのリストの一部である各列の行数を含める必要があります。

新しい要素を追加してこの配列を更新した後、この新しい列挙点のすぐ右下にあるグリッドの正方形がすでに候補リストにあるかどうかを判断するために、両側の列のサイズを確認します。

左側の列のサイズを確認してください。これよりも大きい場合は、新しい列挙ポイントの下に要素を追加する必要はありません。

右側の列のサイズを確認してください。この列の同じサイズより1つ小さい場合は、この列の右側の要素を更新する必要はありません。

これを明確にするために、M = 4、N=2のこの部分的に完成したチャートを見てみましょう。

4  3  2  1
*  *  *  2 |2
*  3  2  1 |1

要素（4,2）、（3,2）、（2,2）、および（4,1）はすでにリストに含まれています。（最初の座標はM、2番目はNです。）これは[列挙ポイント]リストにある各列のアイテムの数であるため、列サイズの配列は[2 110]です。新しいリストに（3,1）を追加しようとしています-右側の列サイズを見ると、M = 2の列のサイズが大きいため、（2,1）を追加する必要はないと結論付けることができます。 1-1より。理由は視覚的にはかなり明確です。（2,2）を追加したときにすでに（2,1）を追加しました。

Answer 2

これは O(K logK) ソリューションです。ここで、K は生成する項の数です。
編集: Q は各要素のコピーを 1 つだけ保持します。要素がすでに存在する場合、挿入は失敗します。

priority_queue Q
Q.insert( (N*M, (N,M)) ) // priority, (x,y) 
repeat K times:
    (v, (x,y)) = Q.extract_max()
    print(v, (x,y))
    Q.insert( (x-1)*y, (x-1,y) )
    Q.insert( x*(y-1), (x,y-1) )

(x,y) にアクセスする前に、(x+1,y) または (x,y+1) にアクセスする必要があるため、これは機能します。複雑さは O(KlogK) です。最大で 2K の Q 個の要素がそれにプッシュされるからです。

Answer 3

これがあなたのためのアルゴリズムです。私はあなたに英語の説明を与えようとします。

使用している長方形では、ポイントP(x, y)の「面積」がその下のポイントよりも大きいと常に想定できますP(x, y-1)。したがって、最大面積のポイントを探すときは、各列の最上位の未取得ポイントを比較するだけで済みます（つまり、可能な場合ごとにx）。たとえば、元の3 x 5グリッドを検討する場合

5 a b c
4 d e f
3 g h i
2 j k l
1 m n o
  1 2 3

a実際には、、、bおよびを比較するだけで済みcます。他のすべてのポイントは、それらの少なくとも1つよりも面積が少ないことが保証されています。したがって、各列の最上部のポイントのみを含む最大ヒープを構築します。ヒープからポイントをポップするときは、その真下にあるポイントを押し込みます（そのポイントが存在する場合）。ヒープが空になるまで繰り返します。これにより、次のアルゴリズムが得られます（テスト済みですが、Rubyで使用されています）。

def enumerate(n, m)
    heap = MaxHeap.new
    n.times {|i| heap.push(Point.new(i+1, m))}

    until(heap.empty?)
        max = heap.pop
        puts "#{max} : #{max.area}"

        if(max.y > 1)
            max.y -= 1
            heap.push(max)
        end
    end
end

これにより、実行時間が。になりO((2k + N) log N)ます。ヒープ操作のコストlog N; N最初のヒープを構築するとき、そして最大面積2kのポイントを引き出すときにそれらを行いますk（各ポップの後にその下のポイントがプッシュされると仮定して2）。

セット全体を作成してから並べ替えるという当初の提案とは異なり、すべてのポイントを作成する必要がないという追加の利点があります。ヒープを正確に保つために必要な数のポイントを作成するだけです。

そして最後に： 改善を行うことができます！ 私はこれらを行っていませんが、次の調整を行うことでさらに優れたパフォーマンスを得ることができます。

1. y = xの代わりに、各列でのみ下降しますy = 1。チェックしなくなったポイントを生成するには、の面積がの面積P(x, y)と等しいという事実を使用しP(y, x)ます。 注：この方法を使用する場合は、2つのバージョンのアルゴリズムが必要になります。列はの場合に機能しますが、代わりに行でこれを行う必要M >= Nがある場合。M < N
2. 最大値を含む可能性のある列のみを考慮してください。a私が示した例では、ヒープが。未満であることが保証されているため、最初からヒープに含める理由はありませんb。したがって、隣接する列のトップポイントがポップされたときにのみ、ヒープに列を追加する必要があります。

そして、それは小さなエッセイに変わりました...とにかく-それが役立つことを願っています！

編集： 私が上で述べた両方の改善を組み込んだ完全なアルゴリズム（しかし、私は怠惰なので、まだRubyにあります）。重複の挿入を回避するために余分な構造は必要ないことに注意してください。「最上位」のポイントでない限り、各ポイントは、取得時にその行/列に別のポイントを挿入するだけです。

def enumerate(n, m, k)
    heap = MaxHeap.new
    heap.push(Point.new(n, m))
    result = []

    loop do
        max = heap.pop
        result << max
        return result if result.length == k

        result << Point.new(max.y, max.x) if max.x <= m && max.y <= n && max.x != max.y
        return result if result.length == k

        if(m < n) # One point per row
            heap.push(Point.new(max.x, max.y - 1)) if max.x == n && max.y > 1
            heap.push(Point.new(max.x - 1, max.y)) if max.x > max.y
        else # One point per column
            heap.push(Point.new(max.x - 1, max.y)) if max.y == m && max.x > 1
            heap.push(Point.new(max.x, max.y - 1)) if max.y > max.x
        end
    end
end

Answer 4

わかった！

グリッドを M 列のセットと考えてください。各列は、下部の 1 から上部の N までの要素を含むスタックです。すべての列には、その x 座標がタグ付けされています。

すべての列スタック内の要素は、その y 値によって並べ替えられ、x はすべての要素に対して同じ値を持つため、x*y によって並べ替えられます。

したがって、一番上にある x*y 値が大きい方のスタックを選択し、それをポップして繰り返すだけです。

実際には、スタックは必要ありません。最上位の値のインデックスだけです。プライオリティ キューを使用して、より大きな x*y 値を持つ列を取得できます。次に、インデックスの値を減らし、それが 0 より大きい場合 (スタックが使い果たされていないことを示します)、新しい優先度 x*y でキューにスタックを再挿入します。

N=M の場合のこのアルゴリズムの複雑さは O(N ² logN) であり、そのメモリ使用量は O(N) です。

更新：Perlで実装...

use Heap::Simple;

my ($m, $n) = @ARGV;

my $h = Heap::Simple->new(order => '>', elements => [Hash => 'xy']);
# The elements in the heap are hashes and the priority is in the slot 'xy':

for my $x (1..$m) {
    $h->insert({ x => $x, y => $n, xy => $x * $n });
}

while (defined (my $col = $h->extract_first)) {
    print "x: $col->{x}, y: $col->{y}, xy: $col->{xy}\n";
    if (--$col->{y}) {
        $col->{xy} = $col->{x} * $col->{y};
        $h->insert($col);
    }
}

Answer 5

Haskell では、すぐに出力が生成されます。以下に図を示します。

         -------
        -*------
       -**------
      -***------
     -****------
    -*****------
   -******------
  -*******------

各スター付きポイントは、(x,y) と (y,x) の両方を生成します。アルゴリズムは、各列の上部の要素を比較して、右上隅からこの要素を「食い込み」ます。Nフロンティアの長さは( と仮定します) を超えることはありませんN >= M。

enuNM n m | n<m = enuNM m n                    -- make sure N >= M
enuNM n m = let
    b = [ [ (x*y,(x,y)) | y<- [m,m-1..1]] | x<-[n,n-1..m+1]]
    a = [ (x*x,(x,x)) : 
          concat [ [(z,(x,y)),(z,(y,x))]       -- two symmetrical pairs,
                           | y<- [x-1,x-2..1]  --  below and above the diagonal
                           , let z=x*y  ] | x<-[m,m-1..1]]
 in
    foldi (\(x:xs) ys-> x : merge xs ys) [] (b ++ a)

merge a@(x:xs) b@(y:ys) = if (fst y) > (fst x) 
                            then  y : merge  a ys 
                            else  x : merge  xs b
merge a [] = a 
merge [] b = b

foldi f z []     = z
foldi f z (x:xs) = f x (foldi f z (pairs f xs))

pairs f (x:y:t)  = f x y : pairs f t
pairs f t        = t

foldiは、ヒープとして機能する歪んだ無限に深くなるツリーを構築し、すべてのプロデューサー ストリームを結合します。各 はx、既に降順で並べ替えられて作成されています。プロデューサ ストリームのすべての初期値は降順であることが保証されているため、各初期値を比較せずにポップすることができ、ツリーを遅延構築できます。

のコードはa、対角線の下からの対応するペアを使用して、対角線の上のペアを生成します (仮定の下で、N >= Mそれぞれの(x,y)場所x <= M & y < xで(y,x)も生成されます)。

比較ツリーの最上部に非常に近い、生成されたいくつかの最初の値のそれぞれについて、実質的に O(1) になるはずです。

Prelude Main> take 10 $ map snd $ enuNM (2000) (3000)
[(3000,2000),(2999,2000),(3000,1999),(2998,2000),(2999,1999),(3000,1998),(2997,2
000),(2998,1999),(2999,1998),(2996,2000)]
( 0.01 秒、1045144 バイト)

Prelude Main> let xs=take 10 $ map (log.fromIntegral.fst) $ enuNM (2000) (3000)
Prelude Main> zipWith (>=) xs (tail xs)
 [True,True,True,True,True,True,True,True,True]

Prelude Main> take 10 $ map snd $ enuNM (2*10^8) (3*10^8)
[(300000000,200000000),(299999999,200000000),(300000000,199999999),(299999998,20
0000000),(299999999,199999999),(300000000,199999998),(299999997,200000000),(2999)
99998,199999999),(299999999,199999998),(299999996,200000000)]
( 0.01 秒、2094232 バイト)

経験的な実行時の複雑さを評価できます。

Prelude Main> take 10 $ drop 50000 $ map (log.fromIntegral.fst) $ enuNM (2*10^8)
 (3*10^8)
[38.633119670465554,38.633119670465554,38.63311967046555,38.63311967046554,38.63
311967046554,38.63311967046553,38.63311967046553,38.633119670465526,38.633119670
465526,38.63311967046552]
( 0.17 秒、35425848 バイト)

プレリュード Main> take 10 $ drop 100000 $ map (log.fromIntegral.fst) $ enuNM (2*10^8
) (3*10^8)
[38.63311913546512,38.633119135465115,38.633119135465115,38.63311913546511,38.63
311913546511,38.6331191354651,38.6331191354651,38.633119135465094,38.63311913546
5094,38.63311913546509]
( 0.36 秒、71346352 バイト)

*Main> let x=it
*メイン> zipWith (>=) x (テール x)
 [True,True,True,True,True,True,True,True,True]

Prelude Main> logBase 2 (0.36/0.17) 
1.082462160191973      -- O(n^1.08) for n=100000 値が生成される

これは、ここで見られるように、Haskell ストリームのジェネレーターを使用して、たとえば Python に簡単に変換できます。

Answer 6

これは実質的に素数を列挙することと同じです。必要な数値は、素数ではないすべての数値です ( 1x以上の数値を除くy)。

あなたがすでに提案している方法よりも高速になる素数を列挙する方法があるかどうかはわかりません（少なくともアルゴリズムの複雑さの点では）。

Answer 7

NxM から 1 までループして、乗算すると現在の数値を生成するペアを検索するダミーのアプローチ:

#!/usr/bin/perl

my $n = 5;
my $m = 4;

for (my $p = $n * $m; $p > 0; $p--) {
    my $min_x = int(($p + $m - 1) / $m);
    for my $x ($min_x..$n) {
        if ($p % $x == 0) {
            my $y = $p / $x;
            print("x: $x, y: $y, p: $p\n");
        }
    }
}

N=M の場合、複雑さは O(N ³ ) ですが、メモリ使用量は O(1) です。

更新: 生成する要素の数が既に N ²であるため、複雑さは見かけほど悪くないことに注意してください。比較のために、すべてのペアを生成して並べ替えるアプローチは、O(N ² ) のメモリ使用量で O(N ² logN)です。

Answer 8

ほとんどの場合、シーケンスの最初の数項が必要であると述べているためです。それらをすべて生成した後、これらの最初のいくつかの用語を見つけるためにそれらをすべて並べ替える必要はありません。必要な用語の数 (k など) に応じて最大ヒープを使用できます。したがって、ヒープのサイズが k (<< N && << M) の場合、nlogk の後に最大の k 項を持つことができます。これは、並べ替えに nlogn よりも優れています。

ここで n = N*M