Комбинации символов в массиве символов n по n: - PullRequest
Новая
       30

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

3 голосов
/ 01 февраля 2011

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

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

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

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

Я получил это очень много:

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

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

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

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

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

1 Ответ

1 голос
/ 01 февраля 2011

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

В каждом элементе массива 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 возможных комбинаций строк, то этот алгоритм выполняет около cn шагов для больших n, где c - некоторая постоянная.

...