Perl: пользовательский порядок сортировки?

Question

Стенографическая клавиатура имеет ключи в определенном порядке: STKPWHRAO * # EUFRPBLGTS.

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

Таким образом, KAT будет действительным, но FRAG не будет, потому что в то время как F перед R с правой стороны, они не находятся перед A-. TKPWAUL будет работать, но GAUL не будет, потому что -G не до A. Ключи должны быть заказаны слева направо.

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

Большое спасибо за любые итаи!

Answer 1

Вы можете создать регулярное выражение с якорями для начала и конца строки и разрешить каждый символ 0 или один раз. Вот пример:

sub match { 
    my $yesno = $_[0] =~ /^S?T?K?P?W?H?R?A?O?\*?#?E?U?F?R?P?B?L?G?T?S?\.?$/g; 
    print $_[0] . " " . ($yesno ? 'yes' : 'no') . "\n"; 
} 
match 'KAT'; 
match 'FRAG'; 
match 'TKPWAUL'; 
match 'GAUL'; 

поставляет

KAT yes 
FRAG no 
TKPWAUL yes 
GAUL no 

Вы могли бы генерировать, что регулярное выражение из списка с помощью split, join и т.д.

Answer 2

Вот простой алгоритм. Это должно быть эффективным и также может быть улучшено при необходимости.

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

sub accept_word { 
    my ($refseq, $word) = @_; 
    my ($mark, $pos) = (0, 0); 
    foreach my $ch (split '', $word) { 
     # search until position is >= $mark, or the word is bad 
     while (($pos = index($refseq, $ch, $pos)) != -1) { 
      $mark = $pos, last if $pos >= $mark; 
     } 
     return 0 if $pos < $mark; 
    } 
    return 1; 
} 
for my $word (qw(KAT FRAG TKPWAUL GAUL SAS)) { 
    print "$word is " . (accept_word($refseq, $word) ? 'accepted' : 'rejected') . "\n"; 
} 

Комментарии:

Это может быть затянуты совсем немного, если это необходимо. Поиск может быть значительно оптимизирован, поскольку в начале и конце повторяются только «S» и «T» (см. Комментарии). Или он может быть оптимизирован путем поиска количества букв в первой последовательности (скажем, через ('S' => 2, 'T' => 2, 'K' => 1) и т. Д.), Так что index не делает ненужной работы. См. Комментарий tba для его ссылки на немного более тугое исполнение и эталон между этим и его опубликованным регулярным выражением, в котором используется другой алгоритм.

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

Пройдите контрольную последовательность и после того, как найдена совпадение, запишите ее числовой индекс в последовательности. На первом проходе (символ первого слова) это становится самой высокой позицией, скажем $mark.

Для остальной части итераций необходимо быть осторожным, поскольку эталонная последовательность имеет повторяющиеся символы. (Спасибо за комментарий tba.) Как признается, что символ соответствует в последовательности, индекс совпадения сравнивается с $mark, и если он >=, мы возвращаем $mark и переходим к следующему символу. Если позиция < $mark, поиск и сравнение продолжаются до тех пор, пока не будет найдено >= или последовательность исчерпана, когда слово будет отброшено (символ слева от предыдущего). Улучшение: начните поиск с $mark, и если найдено совпадение, сбросьте $mark и перейдите к следующему символу, иначе слово будет отброшено (сделано через index в приведенном выше коде).Поскольку вы соответствуете символам в своем слове, вы просматриваете ссылочную последовательность и помните, как далеко вы добрались.

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