<jupyter_start><jupyter_text>Set Packing問題この問題はExact Cover問題と似ています。ある自然数の集合Uを考えます。またその自然数を含むいくつかのグループ$V_{1}, V_{2}, \ldots, V_{N}$を想定します。１つの自然数が複数のグループに属していても構いません。さて、そのグループ$V_{i}$からいくつかピックアップしたときに、それらに同じ自然数が複数回含まれず、Uに含まれる自然数セットと同じになるようにピックアップする問題がExact Cover問題でした。このとき、選んだグループ数が最大になるように選ぶ問題をSet Packing問題といいます。  準備blueqatがインストールされていない場合は、環境に併せて以下のようにインストールしてください。<jupyter_code>!pip install blueqat<jupyter_output>Collecting blueqat
[?25l  Downloading https://files.pythonhosted.org/packages/bb/86/1b72a7cbe500b861d63e84cc6383fbf3730f08ae69fcd85146ae8e3b8873/blueqat-0.3.10-py3-none-any.whl (46kB)

[K     |███████                         | 10kB 16.1MB/s eta 0:00:01
[K     |██████████████                  | 20kB 1.9MB/s eta 0:00:01
[K     |█████████████████████▏          | 30kB 2.7MB/s eta 0:00:01
[K     |████████████████████████████▏   | 40kB 1.7MB/s eta 0:00:01
[K     |████████████████████████████████| 51kB 1.7MB/s 
[?25hRequirement already satisfied: numpy~=1.12 in /usr/local/lib/python3.6/dist-packages (from blueqat) (1.17.4)
Requirement already satisfied: scipy>=1.1.0 in /usr/local/lib/python3.6/dist-packages (from blueqat) (1.3.3)
Installing collected packages: blueqat
Successfully installed blueqat-0.3.10<jupyter_text>必要なライブラリをimportし、blueqatオブジェクトをインスタンス化します。<jupyter_code>%matplotlib inline

import numpy as np
import matplotlib.pyplot as plt
import blueqat.opt as wq<jupyter_output><empty_output><jupyter_text>QUBOの作成解きたい問題のコスト関数は$ E = E_{A} + E_{B} $で、$E_{A}, E_{B}$はそれぞれ、$ E _ { A } = A \sum _ { i , j : V _ { i } \cap V _ { j } \neq \emptyset } x _ { i } x _ { j }$$E _ { B } = - B \sum _ { i } x _ { i }$と定義されています。まず、$E_{A}$は、$i \not= j$である$V_{i}, V_{j}$を選んだときに、重複する自然数があったばあいにペナルティを与えることを意味しています。また、$E_{B}$は最も多く選択されている場合に、コストが低くなることを意味しています。係数$A, B$については、1つ多く選ぶ（コストがB下がる）より、重複がない（1つ重複があるとコストがA上がる）ことを優先したいので、$A > B$である必要があります。これをコードにすると次の通りです。<jupyter_code>A = 1.0
B = 0.9

def get_qubo(V):
    Q = np.zeros( (len(V), len(V)) )

    for i in range(len(V)):
        for j in range(i, len(V)):
            if i == j:
                Q[i][j] += -B
            elif len(V[i]) + len(V[j]) != len( set(V[i]) | set(V[j]) ):
                Q[i][j] +=  A

    return Q<jupyter_output><empty_output><jupyter_text>また、結果を表示する関数も定義しておきましょう。<jupyter_code>def show_answer(list_x, energies = None, show_graph = False):
    print("Result x:", list_x)
    text = ""
    for i in range(len(list_x)):
        if(list_x[i]):
            text += str(V[i])
    print("Picked {} group(s): {}".format(sum(list_x), text))
    if energies is not None:
        print("Energy:", a.E[-1])
    if show_graph:
        plt.plot(a.E)
        plt.show()<jupyter_output><empty_output><jupyter_text>次の通り実行してみます<jupyter_code>V = [ [1,2], [3,4,5,6], [7,8,9,10], [1,3,5], [10], [7,9], [2,4,6,8], [1,2,3,4,5,6,8,10] ]
for i in range(5):
    print("---{}回目".format(i+1))
    a = wq.opt()
    a.qubo = get_qubo(V)
    answer = a.sa()
    show_answer(answer, a.E)<jupyter_output>---1回目
Result x: [1, 1, 0, 0, 1, 1, 0, 0]
Picked 4 group(s): [1, 2][3, 4, 5, 6][10][7, 9]
Energy: -3.5999999999999996
---2回目
Result x: [1, 1, 0, 0, 1, 1, 0, 0]
Picked 4 group(s): [1, 2][3, 4, 5, 6][10][7, 9]
Energy: -3.5999999999999996
---3回目
Result x: [0, 0, 0, 1, 1, 1, 1, 0]
Picked 4 group(s): [1, 3, 5][10][7, 9][2, 4, 6, 8]
Energy: -3.6000000000000005
---4回目
Result x: [1, 1, 0, 0, 1, 1, 0, 0]
Picked 4 group(s): [1, 2][3, 4, 5, 6][10][7, 9]
Energy: -3.5999999999999996
---5回目
Result x: [1, 1, 0, 0, 1, 1, 0, 0]
Picked 4 group(s): [1, 2][3, 4, 5, 6][10][7, 9]
Energy: -3.5999999999999996
{'fraction_non_alphanumeric': 0.2094329028635598, 'fraction_numerical': 0.0957327344188658, 'mean_word_length': 3.948611111111111, 'pattern_counts': {'":': 0, '<': 19, '<?xml version=': 0, '>': 21, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 5, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '5', 'dir': 'jupyter-structured-clean-dedup', 'id': '389393', 'license': 'Apache-2.0', 'n_tokens_mistral': 2218, 'n_tokens_neox': 1901, 'n_words': 307, 'path': 'tutorial-ja/313_setpacking_ja.ipynb', 'repo_name': 'KeiichiroHiga/Blueqat-tutorials', 'size': '3562'}