例として、(0,1 ... 15)のような数値のセットを、それ自体に隣接する数値を許可せずに、既知の次元の大きな2D配列に分散させたい:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 1 2 3 4 5 6 7
3 4 5 6 7 8 9 10 11 12 13 14 15 0 1 2 3 4 5 6 7 8 9 10
6 7 8 9 10 11 12 13 14 15 0 1 2 3 4 5 6 7 8 9 10 11 12 13
あなたがどんな数を見ても、あなたはそれがどんな方向にもそれ自身に隣接しているのを見ることは決してないだろうか?
うまくいけばあなたのニーズを満たすであろうあなたが望むことをするためのアルゴリズムを説明します。
最初に元の数値の配列を取得し、それをほぼ同じサイズの4つの配列に分割します(この例では、これは(0,1,2,3)、(4,5,6,7)、 (8,9,10,11)、(12,13,14,15)それが理にかなっている場合)。これらのサブアレイを標識arr1
、arr2
、arr3
、arr4
、それぞれ。
ここで、配列を埋めるには、次のように行を埋めます。行のインデックスが偶数(0番目、2番目、4番目など)の場合は、行の最初の要素にからのラドノム番号を入力arr1
します。行のインデックスが奇数の場合、行に2番目の数値を入力しarr3
ます。次に、配列の次の要素に、次の前の要素の乱数を入力しarr
ます。例えば、行の最初の要素の数であった場合、arr1
後行の次の要素がの要素であろうarr2
、とから以下arr3
、その後arr4
、再びまでarr1
等、そして、それはそれです。
なぜ機能するのか:なぜ機能するのか疑問に思われる場合は、最初に2D配列をグラフとして検討してください。対角線を含めると、2次元配列は彩色番号4color
のグラフになります。つまり、グラフに4つの一意の要素が必要です。これらの色は基本的にarr1
、...、arr4
であるため、グラフにarr
「」の数字を入力すると、グラフを効果的に「色付け」します。
グラフの色を確認するには、4x4配列を検討してください。それはそのように4色にすることができます:
[[ 1 , 2 , 3 , 4 ],
[ 3 , 4 , 1 , 2 ],
[ 1 , 2 , 3 , 4 ],
[ 3 , 4 , 1 , 2 ]]
これは上記のアルゴリズムが何をするかにanalagousであるが、代わりに数1-4の、それは配列から数値を取得する、ことを注意arr1
、...、 arr4
。また、4色がどのm x n
配列にも当てはまり、アルゴリズムの有効性が証明されていることも比較的明らかです(これは特に厳密な証明ではありませんが、うまくいけば理解できます)。
注意すべきことがいくつかあります。まず、少なくとも4の長さの初期配列が必要です。そうでない場合は、使用できる「色」が4つ未満になり、このグラフを3色だけで色付けできないことは簡単にわかります。さらに、このアルゴリズムは確かに改善されて、たとえば、現在のように「よりランダム」に見えるようになります。数値は均等に分散されますがarr1
、たとえばからの数値しか見つからないため、あまりランダムではないように見えます。最終的な配列の特定の場所。しかし、このアルゴリズムは、ほぼ均等に番号を配布する(あれば最高んarr1
、arr2
、arr3
、arr4
全て同じ大きさ)と質問が尋ねたので、私はそれが有効であると考えているものを行います。
グラフ彩色の詳細については、ウィキペディアのページ(数学を多用する)、または関連するこのクールな問題(4色の地図の定理、おそらくあなたはそれに精通していますか?)を読むことをお勧めします。
この回答がお役に立てば幸いです。コメントがあればコメントを残してください。
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加