20212


ary1 = [1, 3, 3, 2, 2, 1]  
を考えることにします。  
1と1を上側で結んで、  
2と2を上側で結んで、  
3と3を上側で結んだとき  
（無理やり結んだ曲線を交差させないかぎり）  
交点は0個です。

一方  
ary2 = [1, 3, 2, 3, 2, 1]  
を考えることにします。  
1と1を上側で結んで、  
2と2を上側で結んで、  
3と3を上側で結んだとき  
交点は1個でできます。

このように、  
ary の中に1～nまでの数字が2個ずつあり、  
同じ数字同士上側で結んだとき、  
交点ができるか否かの判定をするには  
どうすればいいでしょうか？  
（どうもあみだくじのようにはいかない…。）  
考え方でもよいので教えてください。


CC BY-SA 3.0
2015-12-20T08:20:39.180
20208
2015-12-20T10:03:24.220
5363
question
ruby アルゴリズム
同じ数同士線で結んだとき、交点ができるか否かの判定について


BLUEPIXY さんがおっしゃっているように、交点があるかどうかの判定は、入れ子状態になっているかどうかの判定に等しいと思います。

あまり洗練されてないですが、アルゴリズムはこんな感じになると思います。

[code]

    def find_matched(arr,i)
      next_index=i+1
      while next_index && next_index < arr.length
        return next_index + 1 if arr[i] == arr[next_index]
        next_index = find_matched(arr,next_index)
      end
      nil
    end
    
    def test_intersect(arr)
      i=0
      while i && i < arr.length do
        i=find_matched(arr,i)
      end
      i == arr.length
    end
    
    test_intersect([1, 3, 3, 2, 2, 1])
    # => true
    test_intersect([1, 3, 2, 3, 2, 1])
    # => false
    test_intersect([1, 2, 1, 2, 3, 3])
    # => false
    test_intersect([1, 1, 2, 2, 3, 3])
    # => true
    
[/code]


CC BY-SA 3.0
2015-12-20T08:54:41.430
20211
2015-12-20T09:18:21.677
2015-12-20T09:18:21.677
754
754
20208
answer


BLUEPIXYさんが貼られた[括弧のマッチングの例](https://stackoverflow.com/q/30491125/2818869)と同様に、スタックを使った方法で書いてみました。

[code]

    def test_intersect(arr)
        arr.inject([]) do |stack,item|
            stack.last == item ? stack[0..-2] : stack << item
        end == []
    end
    
[/code]

括弧の場合は閉じ括弧があるのでスタックの一番上を見るだけで打ち切り判定ができるのですが、今回の場合1回目なのか2回目なのかわからないので、とりあえず打ち切りなしで実装しました。

なんとなく `inject()` を使いましたが、普通のループで書いた方が効率はいいのかな。


CC BY-SA 3.0
2015-12-20T09:57:00.570
20212
2015-12-20T10:03:24.220
2017-05-23T12:38:55.307
-1
8000
20208
answer