Алгоритм для распределения множества чисел в двумерном массиве без соседних самих себя

Question

Я хочу, чтобы алгоритм распределял набор чисел, таких как (0,1...15), в большой двумерный массив с известными размерами, не позволяя числу, соседствующему себя в качестве примера:

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

если вы посмотрите на какое-либо число, вы никогда не увидите соседнего с ним в любом направлении?

Answer 1

Я опишу алгоритм для выполнения того, что вы хотите, надеюсь, будет соответствовать вашим потребностям.

1. Сначала возьмите исходный массив чисел и разбейте его так, как вы хотите, на 4 массива примерно одинакового размера (в вашем примере это может выглядеть как (0,1,2,3),(4,5,6,7),(8,9,10,11),(12,13,14,15), если это имеет смысл). Пометьте эти подмассивы arr1, arr2, arr3, arr4соответственно.

2. Теперь, чтобы заполнить массив, заполните строки следующим образом: Если строка имеет четный индекс (ноль, второй, четвертый и т. Д.), То заполните первый элемент в строке радном числом из arr1в противном случае, если строка имеет нечетный индекс, заполните строку числом от второго arr3, Затем заполните следующий элемент массива случайным числом из arr следуя предыдущему. Например, если первым элементом строки было число из arr1тогда следующий элемент в строке будет элементом arr2и следующее из arr3, а потом arr4, а затем вернуться к arr1и т. д. И это все.

Почему это работает: Если вам интересно, почему это работает, сначала рассмотрите 2d массив как график. Включая диагонали, массив 2d становится графом с хроматическим числом 4, что означает, что для color график. Эти цвета в основном то, что arr1,..., arr4 так, при заполнении графика числами из arrМы эффективно "раскрашиваем" график.

Чтобы увидеть, как график окрашен, рассмотрим массив 4х4. Это может быть четыре цвета как таковые:

[[ 1 , 2 , 3 , 4 ],
 [ 3 , 4 , 1 , 2 ],
 [ 1 , 2 , 3 , 4 ],
 [ 3 , 4 , 1 , 2 ]] 

Обратите внимание, что это аналогично тому, что делает вышеприведенный алгоритм, но вместо числа 1-4 он получает числа из массивов, arr1,..., arr4, Также относительно ясно видеть, что 4-раскраска верна для любого m x n массив, доказывающий правильность нашего алгоритма (это не особенно строгое доказательство, но, надеюсь, вы поняли идею).

Есть несколько вещей, на которые стоит обратить внимание. Во-первых, вам нужен начальный массив длиной не менее 4, в противном случае, если вы этого не сделаете, у вас будет менее 4 "цветов" для работы, и легко увидеть, что вы не можете раскрасить этот график только тремя цветами. Кроме того, этот алгоритм, безусловно, можно улучшить, скажем, чтобы он казался "более случайным", как сейчас, в то время как числа распределены одинаково, они будут казаться не очень случайными, как число из arr1 например, будет доступен только в определенных местах в конечном массиве. Однако этот алгоритм распределяет числа примерно одинаково (лучше всего, если arr1, arr2, arr3, arr4 все одинакового размера) и делает то, что задает вопрос, поэтому я считаю, что это действительно.

Чтобы больше узнать о раскраске графов, я бы порекомендовал прочитать страницу Википедии (более интенсивную математику) или эту интересную проблему (теорема о 4-х цветных картах, может быть, вы знакомы с ней?).

Надеюсь, что этот ответ поможет, оставьте комментарий, если у вас есть.