Julia小ネタ: IterTools.jl

Juliaの小ネタとして，IterTools.jlを紹介します．Pythonのitertools的なものです．実装の中身は知りませんが．今回は与えられた整数リストの冪集合を見てみましょう．

情報など

• https://juliacollections.github.io/IterTools.jl/stable/

例題その1

• 特に理由はないですが，空集合は面倒なので取り除きました (continue)

using IterTools

n = 4
I = collect(1:n)

for ss in subsets(I)
  length(ss) == 0 && continue
  @show ss
end

出力です

ss = [1]
ss = [2]
ss = [1, 2]
ss = [3]
ss = [1, 3]
ss = [2, 3]
ss = [1, 2, 3]
ss = [4]
ss = [1, 4]
ss = [2, 4]
ss = [1, 2, 4]
ss = [3, 4]
ss = [1, 3, 4]
ss = [2, 3, 4]
ss = [1, 2, 3, 4]

例題その2

• ある集合$I$を考えます (上のソースだとI)
• 要素$i\in I$には重さ$w_i$がランダムに設定されているとします
• 取ることのできる重さの総量は$W$だとします
• 集合$S\subseteq I$のうち，総量制約を満たすものを取り出してみます

using Random
using IterTools

# 集合I
n = 4
I = collect(1:n)

# 総量 (ランダム)
W = rand(7:13)

# 個別の重さ (ランダム)
w = [rand(1:10) for _ in 1:n]

# 和が総量以下になる部分集合
for ss in subsets(I)
    length(ss) == 0 && continue
    Ws = sum(w[i] for i in ss)
    Ws > W && continue
    @show ss, Ws
end

出力の例です

(ss, Ws) = ([1], 9)
(ss, Ws) = ([2], 5)
(ss, Ws) = ([3], 2)
(ss, Ws) = ([1, 3], 11)
(ss, Ws) = ([2, 3], 7)
(ss, Ws) = ([4], 1)
(ss, Ws) = ([1, 4], 10)
(ss, Ws) = ([2, 4], 6)
(ss, Ws) = ([3, 4], 3)
(ss, Ws) = ([2, 3, 4], 8)

以上です