編集履歴

回答編集履歴

バグ修正

2019/03/24 17:00

投稿

スコア0

test CHANGED Viewed

@@ -172,11 +172,11 @@
     def numlist(lst): # 数列をビットパターンのリストに変換
-        return list(map(lambda x: bitpattern(x),lst))
+        return list(map(bitpattern,lst))
-    def bitmask(m): # すべての数のビットの論理和
+    def bitmask(m): # すべての数の論理和
         return functools.reduce(lambda x, y: x | y, m)
@@ -202,27 +202,25 @@
     mlist = numlist(source) # ビットパターンのリスト
-    ncount = numofbits5(bitmask(mlist)) # 数の種類(n個)
+    ncount = numofbits5(bitmask(mlist)) # 数の種類(n 個)
-    (s,e) = (0,length-1) # 直近の結果のインデックス（最短リスト）
+    (s,e) = (0,length) # 直近の結果のインデックス（最短リスト）
     i = 0
-    while i < length - ncount:
+    while ((e-s+1) != ncount) and (i < length - ncount + 1):
-        mm = 0 # mm, k = 0, i
+        mm = 0
-        for j in range(i, min(length, i+e-s)): # for j in range(i, min(length, i+e-s+1)): # 最短リストの長さしか調べない
+        for j in range(i, min(length, i+e-s)): # 最短リスト - 1 の長さしか調べない
-            i = j if mm ^ mlist[j] == 0 else i # k = j if mm ^ mlist[j] == 0 else k # 先行する数字を無視できるか？
+            i = j if mm ^ mlist[j] == 0 else i # 先行する数字を無視できるか？
             mm |= mlist[j] # 累積ビットパターン
             if numofbits5(mm) == ncount: # n 個揃った
-                #print("+:{0},{1} = {2}".format(i,j,j-i+1)) # print("+:{0},{1},{2} = {3}".format(i,k,j,j-k+1))
+                #print("+:{0},{1} = {2}".format(i,j,j-i+1))
-                # i = k # k は不要
                 s,e = (i,j) if (j-i) < (e-s) else (s,e)
@@ -232,10 +230,6 @@
             #print("-:{0},{1}".format(i,j))
-        if (e-s+1) == ncount: # 最短なのは明らか
-            break
         i += 1
     return (s,e)
@@ -266,15 +260,15 @@
     def trimright(ilist): # 右端の重複を排除
-        e = ilist[-1] # e,r = ilist[-1],[]
+        e, leng = ilist[-1], len(ilist)
-        for i in range(-1, (-1) - len(ilist), -1):
+        for i in range(-1, (-1) - leng, -1):
             if e != ilist[i]:
                 break
-        return min(len(ilist)+i+1,len(ilist)-1)
+        return min(leng+i+1,leng-1)
 ```
@@ -317,3 +311,19 @@
 print(findShortest("123345561234456"))
 ```
+### 修正点 (2019-03-25)
+- numlist のラムダ式が冗長なので削除。
+- 直近の結果のインデックス（最短リスト）の初期値を length-1 から length に変更。
+- i の上限に +1
+- while 条件を変更。一度もループしない場合があります。
+- ソースコードをすべて最新に置き換え。
+あれこれ考えた結果、バグが多なりました。申し訳ありません。なにかのお役に立てれば。

ソースコードを修正しました。

2019/03/24 17:00

投稿

退会済みユーザー

スコア0

test CHANGED Viewed

@@ -210,19 +210,19 @@
     while i < length - ncount:
-        mm, k = 0, i
+        mm = 0 # mm, k = 0, i
-        for j in range(i, min(length, i+e-s+1)): # 最短リストの長さしか調べない
+        for j in range(i, min(length, i+e-s)): # for j in range(i, min(length, i+e-s+1)): # 最短リストの長さしか調べない
-            k = j if mm ^ mlist[j] == 0 else k # 先行する数字を無視できるか？
+            i = j if mm ^ mlist[j] == 0 else i # k = j if mm ^ mlist[j] == 0 else k # 先行する数字を無視できるか？
             mm |= mlist[j] # 累積ビットパターン
             if numofbits5(mm) == ncount: # n 個揃った
-                #print("+:{0},{1},{2} = {3}".format(i,k,j,j-k+1))
+                #print("+:{0},{1} = {2}".format(i,j,j-i+1)) # print("+:{0},{1},{2} = {3}".format(i,k,j,j-k+1))
-                i = k
+                # i = k # k は不要
                 s,e = (i,j) if (j-i) < (e-s) else (s,e)
@@ -266,7 +266,7 @@
     def trimright(ilist): # 右端の重複を排除
-        e,r = ilist[-1],[]
+        e = ilist[-1] # e,r = ilist[-1],[]
         for i in range(-1, (-1) - len(ilist), -1):
@@ -277,3 +277,43 @@
         return min(len(ilist)+i+1,len(ilist)-1)
 ```
+### 修正点 (2019-03-24)
+- k を削除する。i を直接変更することで、探索失敗後の探索を効率化。
+- 「最短リストの長さ」しか調べないを「最短リストの長さ - 1」に変更。
+- 「右端の重複を排除」の変数を修正。
+- 例を追加。
+```python3
+def findShortest(numstr):
+    return findMinList(list(map(int, numstr)))
+print(findShortest("11222314113351413141121511"))
+print(findShortest("12223141133514131411215111111111111"))
+print(findShortest("11222314113351413141144444444444444421511"))
+print(findShortest("2314113351413123141133511"))
+print(findShortest("1233455654321234456"))
+print(findShortest("123455551115555555555"))
+print(findShortest("33123456521223456"))
+print(findShortest("123345561234456"))
+```

ビットを数える解を追記

2019/03/23 18:33

投稿

退会済みユーザー

スコア0

test CHANGED Viewed

@@ -125,3 +125,155 @@
 ### 結論 (2019-03-21)
 数字が未知であり、もっとも右端、もっとも左端だけの探索なら早いのですが、**中央の部分リスト**の効率的な探索方法を見つけられませんでした。再帰呼出しの数は文字列の長さに比例して増えてしまいます。未熟なアイデアでした。
+### ビットを数える解 (2019-03-22)
+敗北の証として、ビット 1 を数えることで数が揃っていることを判定するプログラムを書きました。概要は以下のとおり。
+- 1-N の数字は未知である。数字は連続していなくてもよいが、1 -32 までしか許さない。
+- 前処理で、数字 n を 32 ビットのパターンに置き換える。数字ごとにワードの n-1 番目のビットを 1 にする。
+- 前処理で、使われるすべての数字のビットパターンの論理和と個数 K を調べる。
+- 調査対象の数列のビットパターンの論理和をとり、ビットの個数が K なら数字が揃っていると判断する。
+- 直近の最短リストのインデックスを持たせる。最短インデックスが更新される都度、探索の長さが短くなる。
+- 先に同じ数字が出現した場合、排他的論理和を使って無視できるか判定する。(不完全ですが ... )
+ビットの個数を数える方法は、以下の「バージョン5」を引用しました。
+[ビットを数える・探すアルゴリズム](http://www.nminoru.jp/~nminoru/programming/bitcount.html)
+```python3
+import functools
+def findMinList(source):
+    def bitpattern(n): # n-1番目のビットをon
+        return 1 << (n - 1)
+    def numlist(lst): # 数列をビットパターンのリストに変換
+        return list(map(lambda x: bitpattern(x),lst))
+    def bitmask(m): # すべての数のビットの論理和
+        return functools.reduce(lambda x, y: x | y, m)
+    def numofbits5(bits): # 1のビットの数を数える http://www.nminoru.jp/~nminoru/programming/bitcount.html
+        bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555)
+        bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333)
+        bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f)
+        bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff)
+        return (bits & 0x0000ffff) + (bits >>16 & 0x0000ffff)
+    #print(source)
+    length = len(source) # リストの長さ
+    mlist = numlist(source) # ビットパターンのリスト
+    ncount = numofbits5(bitmask(mlist)) # 数の種類(n個)
+    (s,e) = (0,length-1) # 直近の結果のインデックス（最短リスト）
+    i = 0
+    while i < length - ncount:
+        mm, k = 0, i
+        for j in range(i, min(length, i+e-s+1)): # 最短リストの長さしか調べない
+            k = j if mm ^ mlist[j] == 0 else k # 先行する数字を無視できるか？
+            mm |= mlist[j] # 累積ビットパターン
+            if numofbits5(mm) == ncount: # n 個揃った
+                #print("+:{0},{1},{2} = {3}".format(i,k,j,j-k+1))
+                i = k
+                s,e = (i,j) if (j-i) < (e-s) else (s,e)
+                break
+        #else:
+            #print("-:{0},{1}".format(i,j))
+        if (e-s+1) == ncount: # 最短なのは明らか
+            break
+        i += 1
+    return (s,e)
+```
+### 探索回数を減らす
+改善案として、前処理で左端と右端の重複する数字の無視をあげておきます。
+```python3
+    def trimleft(ilist): # 左端の重複を排除
+        s = ilist[0]
+        for i in range(len(ilist)):
+            if s != ilist[i]:
+                break
+        return max(0,i-1)
+    def trimright(ilist): # 右端の重複を排除
+        e,r = ilist[-1],[]
+        for i in range(-1, (-1) - len(ilist), -1):
+            if e != ilist[i]:
+                break
+        return min(len(ilist)+i+1,len(ilist)-1)
+```

結論を追加

2019/03/22 13:25

投稿

退会済みユーザー

スコア0

test CHANGED Viewed

@@ -112,10 +112,16 @@
 - できれば、インデックスの分布表を一度だけ作成し、それを複製、変形することで解を得たい。
-- 数列が短ければ効率が悪いかもしれないが、長くなれば効率がよくなるのではなかろうか。
+- ~~数列が短ければ効率が悪いかもしれないが、長くなれば効率がよくなるのではなかろうか。~~
 - 再帰関数を参照透過にすれば、部分解を得るのに並行処理などが可能になるだろう。
 簡単な動作確認を行いましたが詳細まで詰めきれていません。問題点をご指摘ください。
+### 結論 (2019-03-21)
+数字が未知であり、もっとも右端、もっとも左端だけの探索なら早いのですが、**中央の部分リスト**の効率的な探索方法を見つけられませんでした。再帰呼出しの数は文字列の長さに比例して増えてしまいます。未熟なアイデアでした。