リスト探索の最小化について

Question

こんにちは。

１～ｎまでの数字がランダムに格納されているリストがあったとします。
そのリストの中には1～ｎの数字が少なくとも一つは必ずある場合、1～ｎを含む部分的なリストの長さの最小値を求めたいのですが
このような時はどのような考え方をすればよろしいのでしょうか？

私が考えている案としましては、まずは長さｎで探索して、探索されたものを別のリスト（A）に格納する

そして長さｎで見つからなかった場合は、Aの各要素の一番末尾に、次の要素の一番最後を追加する、というやり方でやればとても効率的な探索ができると思うのですがどうでしょうか？

そして、各要素に何の数字が足りないかを格納するリストを別に作っておけば、探索もとても楽になると思います。

そうなれば計算量も減ると思うのですが、皆さんはどうお考えですか？

皆様ならどうするかを教えてください、お願いいたします。

Comments

[hayataka2049]

問題の説明がよくわからないので、もう少し厳密に定義した上で（リストの長さは？　1～nを含む部分的なリストとは何を意味している？）具体例など示して説明していただけるとわかりやすくなるかと思います。

[babbleman]

すみません、わかりやすく定義します。
とあるリストがあるとします。そこにはランダムな数字が格納されています。
例えば下のようなリストです。（n=5）
[1,4,3,2,1,1,5,2,4]
1から5までの数字をすべて含むもので長さが最小のものはこのリストAのA[1:7]の6ですよね？
これを求めたいです。

[hayataka2049]

投稿ミス

[hayataka2049]

修正依頼欄へのコメントでもいいですが、できれば質問文の編集で対応してください。

[hayataka2049]

あとはアルゴリズムとかのタグを付けておくと良いかと。

[hayataka2049]

ついでに、今思いついている方法を実装したexecutableなpythonコードを載せていただけるとコミュニケーションのすれ違いが生じづらいと思います。

Answer 1

最初に基準を決め、右にスライドしつつ頭を削っていく方法です。

最初に基準を決める。後は１．２．または３．を繰り返します。
１．　　一番左の数字が重複する場合は１桁を残して削除
２－１．一番左の数字が、一番左の数字以外の検索範囲に存在する場合は削除
２－２．一番左の数字が、一番左の数字以外の検索範囲に存在しない場合は、桁数を保持しつつスライド
３．検索範囲にｎ個の数字が含まれない場合も、桁数を保持しつつスライド

わかりにくいので以下、例。

①１桁目から全ての数字が含まれるまでの桁数を調べる。最小桁数を更新する。
②一番左の数字が２桁目以降と被っている時は、１桁分を残して検索範囲から切り捨てる。最小桁数を更新する。
③一番左の数字が一番左の数字以外の検索範囲の中に含まれる場合、一番左の数字を検索範囲から切り捨てる。最小桁数を更新する。
④②と同じ。
⑤③と同じだが、一番左の数字が一番左の数字以外の検索範囲の中に含まれていない。検索範囲の右側から一番左の数字を探していく。
そして、見つけた箇所から左に最小桁数分を検索範囲とする。
⑥全ての数字が含まれない為、桁数を維持しスライドする。
⑦⑥と同じ。
⑧一番左の数字が２桁目以降と被っていないので、②で行った切捨てはなし。③と同じく一番左の数字が検索範囲の中に含まれているので、一番左の数字を検索範囲から切り捨てる。最小桁数を更新する。
⑨一番左の数字が２桁目以降と被っていないので、②で行った切捨てはなし。⑤と同じく一番左の数字が検索範囲の中に含まれていない。検索範囲の右側から一番左の数字を探すが、存在しないため処理終了。

抜けがある場合ご指摘ください。

＜＜＜追記＞＞＞
⑥⑦のスライド部分は、⑤のように
見つからない数字を探し、その桁から左側に最小桁数分を取る、
のほうが早いですね。

(例：最小桁数７桁とする)
(1)１～７桁目に５がないので、８桁目より右側の５を探す。

１２３４１２３<１４２１４１３５１４２５３１２２１　：　(１～７桁)

(2)１５桁目にあるので、右端を１５桁目として７桁分取る
１２３４１２３１>４１１４１３５<１４２５３１２２１　：　(９～１５桁)
９～１５桁目に２がないので、１６桁目より右側の２を探す。
(3)１８桁目にあるので、右端を１８桁目として７桁分取る
１２３４１２３１４１１>４１３５１４２<５３１２２１　：　(１２～１８桁)
全てあるので検索再開。

Comments

[Lhankor_Mhy]

123455551115555555555
とかだと、上手く行かなさそうな気がします。

[torisan]

①の時点で条件を満たしていると思います。

[babbleman]

少し気になったのが④→⑤のスライドを行う時に、例えばこの問題でいうと13桁目の「5」を先頭にして探索を行うなどの事例は考えなくても大丈夫なのでしょうか？

[torisan]

はい考慮しなくでも大丈夫です、２が見つかった位置で問題ありません。
仮に、後ろに２が存在しない場合はそのまま検索終了です。

[退会済みユーザー]

より短いものを探すという条件を満たさないから。素晴らしい。拍手。

Answer 2

分析

この課題の規則を考えました。規則が多い方が効率的な探索ができると思うからです。

問題の性質(規則)

• 1-nまでの数は必ずしも連続していなくてよい。
• 最小の部分リストには1-nまでの数字が最低1回出現する。

最小の部分リストは最も短く、1-nまでの数字の出現度数の合計が最小。

• 最小の部分リストの両端の数字の出現度数はそれぞれ1である。

もしも出現度数が1より大きればその端点を削除してより短くすることができる。

• 探索開始時に左右両端で同じ数字が連続する場合は、同一の数字を内側に向かって削除して1つにまとめることができる。同型な文字列。

例

11111111111112334556543212344566666
1233455654321234456 <-- 同値変形

解の候補となる部分リスト

• 12334556 左端の部分リスト
• 654321 中央の部分リスト(最小)
• 1234456 右端の部分リスト

一回のスキャンで下記のインデックスの分布表を作成することができます。この表から解法をみつけようとします。

数字	インデックスの分布	出現度数
1	0,12	2
2	1,11,13	3
3	2,3,10,14	4
4	4,9,15,16	4
5	5,6,8,17	4
6	7,18	2

アルゴリズム

右端と左端と中央で最小リストを発見します。左右は簡単に見つかりますが、中央は見つけにくいです。

探索

• 左右両端に同じ数字が連続する場合は、同一の数字を内側に向かって削除して1つにまとめる。
• もっとも左側の部分リスト (1) min(分布の左端のインデックス) 〜 (2) max(分布の左端のインデックス)

(2)を固定、(1)から右側へ出現度数が1になる数字に出会うまで端点を削除する。<-- 実際は行わない

• もっとも右側の部分リスト (1) min(分布の右端のインデックス) 〜 (2) max(分布の右端のインデックス)

(1)を固定、(2)から左側へ出現度数が1になる数字に出会うまで端点を削除する。<-- 実際は行わない

判断

• もっとも左側の部分リストともっとも右側の部分リストが一致または端点を共有するなら、短いほうを採用して探索終了。この部分リストを(A)とする。
• もっとも左側の部分リストともっとも右側の部分リストが一致しないなら、両方(短いほう?)に再帰的な探索処理を実行する。

追加の探索

• 中央の部分リスト

もっとも左側の部分リストの左端点と、もっとも右側の部分リストの右端点を除き、内側の数列に再帰的な探索処理を実行する。左端点も右端点も出現度数が1で削除できない場合は、再帰探索しない。得られた部分リストを(B)とする。

結果

• 最小の部分リスト

(B)と左右の(A)と比較して短いほうが求める解。

自己評価

• できれば、インデックスの分布表を一度だけ作成し、それを複製、変形することで解を得たい。
• 数列が短ければ効率が悪いかもしれないが、長くなれば効率がよくなるのではなかろうか。
• 再帰関数を参照透過にすれば、部分解を得るのに並行処理などが可能になるだろう。

簡単な動作確認を行いましたが詳細まで詰めきれていません。問題点をご指摘ください。

結論 (2019-03-21)

数字が未知であり、もっとも右端、もっとも左端だけの探索なら早いのですが、中央の部分リストの効率的な探索方法を見つけられませんでした。再帰呼出しの数は文字列の長さに比例して増えてしまいます。未熟なアイデアでした。

ビットを数える解 (2019-03-22)

敗北の証として、ビット 1 を数えることで数が揃っていることを判定するプログラムを書きました。概要は以下のとおり。

• 1-N の数字は未知である。数字は連続していなくてもよいが、1 -32 までしか許さない。
• 前処理で、数字 n を 32 ビットのパターンに置き換える。数字ごとにワードの n-1 番目のビットを 1 にする。
• 前処理で、使われるすべての数字のビットパターンの論理和と個数 K を調べる。
• 調査対象の数列のビットパターンの論理和をとり、ビットの個数が K なら数字が揃っていると判断する。
• 直近の最短リストのインデックスを持たせる。最短インデックスが更新される都度、探索の長さが短くなる。
• 先に同じ数字が出現した場合、排他的論理和を使って無視できるか判定する。(不完全ですが ... )

ビットの個数を数える方法は、以下の「バージョン5」を引用しました。
ビットを数える・探すアルゴリズム

import functools
def findMinList(source):

    def bitpattern(n): # n-1番目のビットをon
        return 1 << (n - 1)

    def numlist(lst): # 数列をビットパターンのリストに変換
        return list(map(bitpattern,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) # 直近の結果のインデックス（最短リスト）
    i = 0
    while ((e-s+1) != ncount) and (i < length - ncount + 1):
        mm = 0
        for j in range(i, min(length, i+e-s)): # 最短リスト - 1 の長さしか調べない
            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))
                s,e = (i,j) if (j-i) < (e-s) else (s,e)
                break
        #else:
            #print("-:{0},{1}".format(i,j))
        i += 1
    return (s,e)

探索回数を減らす

改善案として、前処理で左端と右端の重複する数字の無視をあげておきます。

    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, leng = ilist[-1], len(ilist)
        for i in range(-1, (-1) - leng, -1):
            if e != ilist[i]:
                break
        return min(leng+i+1,leng-1)

修正点 (2019-03-24)

• k を削除する。i を直接変更することで、探索失敗後の探索を効率化。
• 「最短リストの長さ」しか調べないを「最短リストの長さ - 1」に変更。
• 「右端の重複を排除」の変数を修正。
• 例を追加。

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-25)

• numlist のラムダ式が冗長なので削除。
• 直近の結果のインデックス（最短リスト）の初期値を length-1 から length に変更。
• i の上限に +1
• while 条件を変更。一度もループしない場合があります。
• ソースコードをすべて最新に置き換え。

あれこれ考えた結果、バグが多なりました。申し訳ありません。なにかのお役に立てれば。

Comments

[babbleman]

凄くわかりやすい回答をありがとうございます！今一度じっくり読ませていただきます。

Answer 3

すみません、これ、ダメですね。

末尾からひとつつづ除去していって、それ以上取れなくなったら先頭から同じことをする、というクソ真面目なアルゴリズムが一番効率がよさそうな気がします。

import random
n = 4

N = 50
L = [random.randint( 0, n - 1 ) for i in range( N ) ]

cloneL = L[:]
itemsNum = [ cloneL.count(x) for x in range( 0, n ) ]

for i in range( N ):
    cuttedItem = cloneL.pop()
    itemsNum[cuttedItem] -= 1
    print(itemsNum)
    if min( itemsNum ) == 0:
        itemsNum[cuttedItem] += 1
        cloneL.append( cuttedItem )
        break

for i in range( N ):
    cuttedItem = cloneL.pop(0)
    itemsNum[cuttedItem] -= 1
    print(itemsNum)
    if min( itemsNum ) == 0:
        itemsNum[cuttedItem] += 1
        cloneL.insert( 0, cuttedItem )
        break

print( len(cloneL), cloneL, L )

おそらく、キモは、いちいちユニークチェックをしなくていいように、最初にリストをなめて要素ごとのカウンタを別に持っておくことではないかと。

Comments

[Lhankor_Mhy]

N>>nなら、ユニークチェックのコストにもよるけど、ご質問者のアルゴリズムの方が効率的かもですね。

[Lhankor_Mhy]

あ、違う、これ、ダメか。