リスト内のすべての一致する要素の位置

Question

私はCommon Lispで、組み込みの位置関数と同様に、針と一致するすべての要素の位置のリストを返します。ちょうど最初の。私はいくつかの可能な解決策を考え出しました（たとえば、位置のcdr-from関数を使用して次の要素を再帰的に検索し、その結果を前の位置に追加するなど）特に優雅に見えます。

誰も私が現在苦労しているように、これに近づく最善の方法を提案することができます。

Answer 1

問題を解決する明白な方法は、リストの各要素を順番に調べ、針が出力リストにその位置を集めるのと同じに比較するたびに調べることです。この場合は、haystackの最初から開始しているため、ポジションを取得することは非常に簡単です。 0から始まる現在の位置をカウントするために変数を使用することができます。

したがって、完全なアルゴリズムを文で記述すると、「乾草の針のすべての位置を見つけるヘイスタックの各要素と、要素が針と等しいときに0から始まる位置は、位置を収集します。

LOOP機能は基本的に、反復処理を行いたいときに抜け出すのに適しています。 experienceの後に構文がdescribe formally,に複雑になっても、アルゴリズムの英語の説明をLOOPの本体に入れておくと、うまくいくでしょう。ここでそれを行うには、別の（必ずしも良い）方法だ

(defun all-positions (needle haystack) 
    (labels ((f (n h c r) 
       (if (null h) 
        r 
        (if (eql (car h) n) 
         (f n (cdr h) (1+ c) (cons c r)) 
         (f n (cdr h) (1+ c) r)))))) 
    (reverse (f needle haystack 0 nil))) 

Answer 2

、あなたのようなものを使用することができます。

(defun get-positions (needle haystack) 
    (let ((result nil)) 
    (dotimes (i (length haystack)) 
     (if (eq (nth i haystack) needle) 
      (push i result))) 
    (nreverse result))) 

Answer 3

：あなたは再帰関数ではなく、(loop ...)基づくものにしたい場合は

 
(defun all-positions (needle haystack) 
    (loop 
    for element in haystack 
    and position from 0 
    when (eql element needle) 
     collect position)) 

Answer 4

塩の粒で、このいずれかを実行します（と事前Alexandriaロードしてください）：

(defun positions (item sequence &key (test #'eql)) 
    (mapcar #'car 
      (remove item (map 'list #'cons (alexandria:iota (length sequence)) sequence) 
         :test-not test 
         :key #'cdr))) 

言った、それは任意の順序で作業の利点を持っている：

CL-USER> (positions 'x #(x x y y x x y y)) 
(0 1 4 5) 
CL-USER> (positions 5 (list 5.0 -1 5 5.0 -1) :test #'=) 
(0 2 3) 
CL-USER> (positions #\l "Hello") 
(2 3)