randomPythonScripts/knapsack3bags.py at master · jojofranz/randomPythonScripts · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
"""
Created on Mon Nov 26 16:36:53 2018

@author: johannes
"""

import numpy as np
items = np.array(['cake', 'plant', 'TV', 'pepernoten'])


# Our new method for 2 bags
def weirdPowerSet(items):
    """ try to stick to the binary solution, but instead
        1. draw more numbers/binary combinations   2**(N*2) instead of 2**N
            the assumption is that 2**(N*2) - x == 3**N
            where x is the number of skipped numbers (see 3.)
        2. map them into onto two different bags
            e.g. number is i = 16   so,   np.binary_repr(16) = '10000'
            this number has to provide information about "taking the item" for two bags
            so, with 4 items we need 2*4=8 bits of information
            so, we use   np.binary_repr(16, 8) = '00010000'   in order to pad zeros to get 8 bits
        3. we have to avoid a situation in which we put an item into both bags at once

        Caveat: building a generator would be awkward because
            you have to yield a result every time (but see powerSet2_1)
        """
    N = len(items)
    combo = []

    # initialize counter for garbage solutions
    x = 0

    # get information (numbers)
    for i in range(2**(N*2)):

        # map information into a binary code of sufficient length
        #   use list comprehension to cast characters as integers
        both = [int(ix) for ix in list(np.binary_repr(i, 2*N))]
        # use the first half of the binary code as information for the first bag
        #   prepare for logical indexing by casting of integers as booleans
        index1 = np.array(both[:N], dtype=bool)
        # use the 2nd half as info for the 2nd bag
        index2 = np.array(both[N:], dtype=bool)

        # discard combinations that would place an item into both bags at once
        if any(index1*index2):
            # count those garbage solutions
            x += 1
            pass

        # accept all other cobinations
        #   use logical indexing to get items
        else:
            combo.append([items[index1].tolist(), items[index2].tolist()])

    return combo, x


pSet, x = weirdPowerSet(items)


# Their Method (gold standard) adapted for 2 bags
def powerSet2(items):
    """returns a generator"""
    N = len(items)
    # enumerate the 2**N possible combinations
    for i in range(3**N):
        combo = ([], [])
        for j in range(N):
            # test bit jth of integer i
            if (i // 3**j) % 3 == 1:
                combo[0].append(items[j])
            if (i // 3**j) % 3 == 2:
                combo[1].append(items[j])
        yield combo


def powerSet2_1(items):
    """returns a list (of list(of lists))"""
    N = len(items)
    combo = []
    # enumerate the 2**N possible combinations
    for i in range(3**N):
        combo1 = []
        combo2 = []
        for j in range(N):
            # test bit jth of integer i
            if (i // 3**j) % 3 == 1:
                combo1.append(items[j])
            if (i // 3**j) % 3 == 2:
                combo2.append(items[j])
        combo.append([combo1, combo2])
    return combo


gs_pSet = powerSet2_1(items)


# Verification 1
if ((2**(len(items)*2)) - x) == (3**len(items)):
    print("Success1: \t Both implementations resulted in the same number of combinations.")
    print(str((2**(len(items)*2)) - x) + " = 2**(N*2) = " + str(3**len(items)) + " = 3**N")
else:
    print("Fail1: \t The two implementations resulted in a different number of combinations.")
    print(str((2**(len(items)*2)) - x) + " = 2**(N*2) != " + str(3**len(items)) + " = 3**N")

# Verification 2
if sorted(pSet) == sorted(gs_pSet):
    print("Success2: \t Both implementations resulted in identical combinations.")
else:
    print("Fail2: \t The two implementations did NOT result in identical combinations.")


# Generator implementation using absolutely excessive list comprehension
def powerSet2_1(items):
    """returns a generator"""
    N = len(items)
    comboI =  [[c[0], c[1]] for c in [[b[:N], b[N:]] for b in [np.array(list(np.binary_repr(i, 2*N)), dtype=int).astype(bool) for i in range(2**(N*2))]] if not any(c[0]*c[1])]

    for i in range(len(comboI)):
        yield ([items[comboI[i][0]], items[comboI[i][1]]])


pGen = powerSet2_1(items)
for i in range(3**len(items)):
    print(next(pGen))