Комбинации символов в n-м массиве символов:

Question

Первое примечание: Извините, что мои изображения не разделены. Я новый участник, поэтому у меня недостаточно очков репутации, чтобы размещать больше, чем одну гиперссылку.

Пусть M представляет собой матрицу n по n (математически квадратную матрицу) символов.

В M, мне нужно уметь находить все перестановки символов с ограничением. Перестановки не должны быть линейными, но они должны содержать символы, в которых каждый символ смежно по меньшей мере с одним другим символом в перестановке. Ниже приведен пример приемлемой перестановки:

Ниже приведена неприемлемая перестановка.

Я вывел это много:

• Перестановка может иметь более п квадрат символов в нем (как никакие символы не могут повторяться).
• Я не знаю точное количество перестановок с учетом ограничений, но я считаю, что может быть не больше значения, генерируемого путем вычисления выражения, изображенного в гиперссылке.

Я могу легко найти перестановки, которые содержат только символы в прямых линиях: вертикальные линии, горизонтальные линии и диагонали. Я не уверен в возможности исчерпывающе найти все остальные перестановки.

Я провел исследование и не смог найти решение подобной проблемы.

Любой совет в разработке такого исчерпывающего алгоритма будет с благодарностью оценен.

http://i.stack.imgur.com/uDNfv.png

Answer 1

Один алгоритма приходит на ум сразу же, хотя оптимизация может быть сделана, если временная сложность вызывает беспокойство.

На каждом элементе массива 2x2 (или мы можем назвать его матрицей, если хотите), есть 8 направлений, которые мы можем путешествовать (север, северо-восток, восток, юг, юг, юго-запад, запад, северо-запад).

Псевдо код мяса алгоритма идет немного как это (я предполагаю передать по значению, так что «current_string» новая строка при каждом вызове функции):

find(position, direction, current_string){ 
    new_letter = m[0, position + direction]; 
    if(!current_string.Contains(new_letter)){ 
     // We have not yet encountered this letter during the search. 
     // If letters occur more than once in the array, then you must 
     // assign an index to each position in the array instead and 
     // store which positions have been encountered along each 
     // search path instead. 
     current_string += new_letter; 
     find(position, (0, 1), current_string); 
     find(position, (1, 1), current_string); 
     find(position, (1, 0), current_string); 
     find(position, (1, -1), current_string); 
     find(position, (0, -1), current_string); 
     find(position, (-1, -1), current_string); 
     find(position, (-1, 0), current_string); 
     find(position, (-1, 1), current_string); 
    } else { 
     // This letter has been encountered during this path search, 
     // terminate this path search. See comment above if letters 
     // occur more than once in the matrix. 
     print current_string; // Print one of the found strings! 
    } 
} 

Теперь вам нужно чтобы добавить некоторые проверки для таких вещей, как «позиция + направление за пределами массива, если да, напечатайте current_string и завершите».

Идея высокого уровня алгоритма выше - поиск по всем возможным путям рекурсивно, завершающие пути при их запуске (точно так же, как змеи умирают в игре Snake).

Если вы используете хеширование для проверки содержания новой буквы в отношении текущей строки (согласно строке if(!current_string.Contains(new_letter)){), которая представляет собой амортизацию O (1) поиска, то сложность выполнения этого алгоритма наихудшего случая является линейной по числу возможных строк в матрице. То есть если в матрице имеется n возможных комбинаций строк, то для больших n этот алгоритм берет около cn шагов, где c - некоторая константа.