【備忘録】bit全探索

python3
あくまで備忘録なんで雑に記録します

①bit全探索の使い方

2^nの全探索(重複順列)を処理したかったのですが、やり方がわからず調べて「bit全探索」に辿り着きました。自分の勉強のため、引用元の方と同じ様な記事になります。
※ただし、O(2^n)なことには注意!

n = 2〜3位なら for を積み重ねるのも良いけど、n自体が変数なら無理
2^100 → 31桁(1267650600228229401496703205376)

問題

引用

(引用)

問題文
みかん(100円)りんご(200円)ぶどう(300円)がそれぞれ1つずつ果物屋さんにありました。財布の中には300円ありますが、考え得るすべての買い物パターンを列挙しなさい。

Python de アルゴリズム(bit全探索)より引用

2^3の8通りで
なし:0円❌
みかん:100円⭕️
りんご:200円⭕️
ぶどう:300円⭕️
みかん・りんご:300円⭕️
みかん・ぶどう:400円❌
りんご・ぶどう:500円❌
みかん・りんご・ぶどう:600円❌

n種類の果物として、10進数No.は「2^n」
bit表示の左から右までの幅が「n」

ここまでは簡単に思いつけるかもしれなかったけど、各判定に

『bit表示を1の位までシフトして、001と&(論理積)をとる』というのは目から鱗
例えば
パターン3のみかんは、2ビット右へシフトして&1でFalse
パターン2のりんごは、1ビット右へシフトして&1でTrue10

mikan = 100
ringo = 200
budou = 300
A = [mikan, ringo, budou]
B = ['みかん', 'りんご', 'ぶどう']

count = 0

for i in range(2**3): #10進数No.でまわしていく
    nedan = 0
    bag = []
    for j in range(3): #iは右から、ぶどうが0、りんごが1、みかんが2
        if (i >> j) & 1 == True: #==Trueはなくてもけれど敢えて
            nedan += A[-(j+1)] #右からj+1番目だから
            bag.append(B[-(j+1)]) #バッグにもいれていく
    if nedan != 0 and nedan <= 300: #0円も省いて300円以下をカウント
        count += 1
        print(bag,nedan) #都度プリント

print('全部で', count, 'パターン')

コメント

"+r+""+h+""+">"}var c,i=n(45),u=n(74),f=n(64),s=n(53),p=n(76),l=n(41),y=(n=n(52),"prototype"),h="script",v=n("IE_PROTO"),g=function(){try{c=new ActiveXObject("htmlfile")}catch(r){}var r;g="undefined"==typeof document||document.domain&&c?function(r){r.write(a("")),r.close();var t=r.parentWindow.Object;return r=null,t}(c):((r=l("iframe")).style.display="none",p.appendChild(r),r.src=String("javascript:"),(r=r.contentWindow.document).open(),r.write(a("document.F=Object")),r.close(),r.F);for(var t=f.length;t--;)delete g[y][f[t]];return g()};s[v]=!0,t.exports=Object.create||function(t,e){var n;return null!==t?(o[y]=i(t),n=new o,o[y]=null,n[v]=t):n=g(),e===r?n:u.f(n,e)}},function(r,t,e){var n=e(5),o=e(44),a=e(43),c=e(45),i=e(11),u=e(75);t.f=n&&!o?Object.defineProperties:function(r,t){c(r);for(var e,n=i(t),o=u(t),f=o.length,s=0;s=t||56320!=(64512&i(r,e))))return!1}return!0}})},function(r,t,e){var n=e(91),o=String;r.exports=function(r){if("Symbol"===n(r))throw new TypeError("Cannot convert a Symbol value to a string");return o(r)}},function(r,t,e){var n=e(2),o=e(7),a=e(13),c=e(15),i=e(102),u=(e=e(6),Array),f=a("".charAt),s=a("".charCodeAt),p=a([].join),l="".toWellFormed,y=l&&e((function(){return"1"!==o(l,1)}));n({target:"String",proto:!0,forced:y},{toWellFormed:function(){var r=i(c(this));if(y)return o(l,r);for(var t=r.length,e=u(t),n=0;n
タイトルとURLをコピーしました