Perl：自定義排序順序？

Question

速記鍵盤具有特定順序的鍵：STKPWHRAO *＃EUFRPBLGTS。

我正在嘗試輸入$字，並確定它的字母是否遵循此順序，從左到右。

所以KAT是有效的，但FRAG不會，因爲雖然F在右邊R之前，但它們不在A-之前。 TKPWAUL會工作，但GAUL不會，因爲-G不在A之前。鍵必須從左到右排列。

我被一些字母在訂單中出現兩次而絆倒。

非常感謝您的任何ieas！

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重置爲$mark，並移至下一個字符，否則該字將被丟棄（通過上面代碼中的index完成）。當你在你的字中匹配字符時，你正在爬取參考序列並記住你有多遠。

這種方式將單詞映射到基於參考字符串的非遞減數字序列，或丟棄。在上面的代碼中，如果需要，可以記錄數字編碼。