質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.50%

  • Python

    10811questions

    Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

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

受付中

回答 3

投稿

  • 評価
  • クリップ 2
  • VIEW 199

babbleman

score 11

こんにちは。

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

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

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

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

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

皆様ならどうするかを教えてください、p

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • hayataka2049

    2019/03/10 20:45 編集

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

    キャンセル

  • hayataka2049

    2019/03/10 20:46

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

    キャンセル

  • hayataka2049

    2019/03/10 21:34 編集

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

    キャンセル

回答 3

+2

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

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

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

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

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

(例:最小桁数7桁とする)
(1)1~7桁目に5がないので、8桁目より右側の5を探す。
>1234123<14214135142531221 : (1~7桁)
(2)15桁目にあるので、右端を15桁目として7桁分取る
12341231>4114135<142531221 : (9~15桁)
9~15桁目に2がないので、16桁目より右側の2を探す。
(3)18桁目にあるので、右端を18桁目として7桁分取る
12341231411>4135142<531221 : (12~18桁)
全てあるので検索再開。

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/03/15 19:48

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

    キャンセル

  • 2019/03/18 08:49

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

    キャンセル

0

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

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

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 )


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

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/03/15 19:36

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

    キャンセル

  • 2019/03/15 19:37

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

    キャンセル

0

分析

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

問題の性質(規則)

  • 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(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)

探索回数を減らす

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

    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)

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

同じタグがついた質問を見る

  • Python

    10811questions

    Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。