2

すべての行と列が個別に要素がペアごとに異なるという特性を持つように、1からKまでの範囲の整数のNxN行列をランダムに生成する必要があります。

たとえば、N=2およびK=3の場合

これで結構です：

1 2
2 1

これではありません：

1 3
1 2

（K <Nの場合、これは不可能であることに注意してください）

KがNよりも十分に大きい場合、1..K整数のランダム行列を生成するだけの効率的なアルゴリズムがあります。各行と各列がペアごとに異なることを確認し、再試行しない場合は。

しかし、KがNよりもそれほど大きくない場合はどうでしょうか。

4

3 に答える 3

1

これは完全な答えではありませんが、機能しない直感的なソリューションについての警告です。「ランダムに生成する」とは、既存のそのようなすべての行列で均一な確率を意味すると仮定しています。

N=2 および K=3 の場合、セット [1..K] の順列までの可能な行列を以下に示します。

1 2    1 2    1 2
2 1    2 3    3 1

(セット [1..K] の順列を無視しているので、最初の行は wlog であると想定できます1 2)。

ここで、直観的な (しかし正しくない) 戦略は、マトリックス エントリを 1 つずつ描画し、各エントリが同じ行または列の他のエントリと区別されるようにすることです。なぜそれが間違っているのかを理解するために、これを描いたと考えてください:

1 2
x .

そして今xを描いています。x は 2 または 3 ですが、それぞれの可能性に 1/2 の確率を与えると、行列は

1 2
3 1

最後に描画される確率は 1/2 ですが、確率は 1/3 しかありません。

于 2012-08-08T09:08:24.257 に答える
0

これが（テキストの）解決策です。ランダム性が良いとは思いませんが、それでもアプリケーションには問題ない可能性があります。

次のアルゴリズムを使用して、[0; K-1]の範囲の行列を生成しましょう（必要に応じて、すべての要素に対して+1を実行します）。

  • 必要なランダムな方法で最初の行を生成します。
  • 各数値は、後続の行に重複がないことが保証されるように計算されたランダムシーケンスの最初の要素になります。つまり、xとyの個別の列に対して、x [i]！=y[iになります。 ][0;N-1]のすべてのiに対して。
  • 前の行の各行を計算します。

すべてのアルゴリズムは、私が言及したプロパティを持つランダムジェネレータに基づいています。簡単に検索すると、Inversive合同法がこの要件を満たしていることがわかりました。実装は簡単なようです。Kが素数の場合に機能します。Kが素数でない場合は、同じページの「複合反転ジェネレータ」を参照してください。完全な平方数や3乗数で処理するのは少し難しいかもしれませんが（問題は数独のように聞こえます:-)）、素因数Kと異なるパラメーター化を使用して複合ジェネレーターを作成することで可能だと思います。すべてのジェネレーターで、各列の最初の要素はシードです。

Kの値が何であれ、複雑さはNにのみ依存し、O（N ^ 2）です。

于 2012-08-08T11:47:44.040 に答える
0
  1. 行と列の目的のプロパティを持つ行列を決定論的に生成します。K > N の場合、これは i 番目の行を i で開始し、行の残りを i+1、i+2 などで埋め、K の後に 1 に戻すことで簡単に実行できます。他のアルゴリズムも可能です。
  2. 列をランダムに並べ替え、次に行をランダムに並べ替えます。

行の並べ替え (つまり、行全体を取り出して、各行が異なる垂直位置にある可能性がある順序でそれらから新しい行列を組み立てること) が、以前は true であったと仮定して、行と列の両方に目的のプロパティをそのまま残すことを示しましょう。同じ理由が、列の順列、およびいずれかの種類の順列の任意のシーケンスにも当てはまります。

  1. 自明なことですが、行を並べ替えても、各行内で複数回出現する要素がないというプロパティを変更することはできません。
  2. 特定の列で行を並べ替えると、その列内の要素が並べ替えられます。これはどの列にも当てはまります。要素を並べ替えても、以前には存在しなかった重複要素を生成することはできないため、行を並べ替えても、各列内で複数回出現する要素がないというプロパティを変更することはできません。

このアルゴリズムがすべての可能な満足する行列を生成できるかどうか、または可能であればすべての可能な満足する行列を等しい確率で生成できるかどうかはわかりません。私が答えを持っていないもう 1 つの興味深い質問は、次のとおりです。より正確には、row-perm-then-column-perm ラウンドの有限シーケンスは、制限された数 (または特に 1 つ) の row-perm-then-column-perm ラウンドと同等ですか? その場合、最初の行と列の順列の後にさらに順列を行っても何も得られません。おそらく、数学のバックグラウンドが強い人がコメントできます。しかし、それで十分な場合もあります。

于 2012-08-09T07:05:40.073 に答える