Python data analysis of lock packing problem problem restatement problem analysis modeling and solution

Python data analysis of lock packing problem problem restatement problem analysis modeling and solution

Problem restatement

A certain factory produces a kind of marble lock, and the height of the slot number can be represented by 5 out of 1 to 6. The restriction is that there are at least 3 different numbers in 5; the height difference between adjacent grooves cannot be 5. In the actual test, it was found that if 4 of the 5 slots corresponding to the two locks are the same in height, and the other one differs by 1, they may be mutually opened, otherwise, they cannot be mutually opened. If 60 locks are packed in a box, ask for the number of locks in a batch and the number of boxes, and ask for a plan to reduce or no longer complain about the group customers, and find the largest non-interchangeable plan for the proposed plan The number of boxes, and measure the degree to which customers complain about each other when they are randomly packed.

problem analysis

  1. The number of locks first abstracts the lock and packing problem into a mathematical concept, and represents a corresponding lock with a qualified combination of 5 numbers or a list data structure, such as [1,2,3,4,5] Represents a lock. Using the idea of ​​elimination, through the Python language, the problem is divided into all possible combinations A6^5, and stored in the list structure; then through the concept of a set, the same slot height in the list is eliminated, and only one is retained. If the number is less than 3 , It does not meet the requirements and is eliminated; finally, the list whose adjacent difference is 5 is eliminated.
  2. Packing scheme design classification method: Divide a batch of locks into two categories or divide them into 20 categories from 8 to 27 according to the sum of their indices. Among them, the combination, [1,1,1,2,3] is the smallest, and the number sum Is 8; [6,6,6,5,4] is the largest, and the sum of its numbers is 27; so there are a total of (27-8+1)=20 arrays, which can be represented by: d9→d11→ …→d27→d 8→d10→d12→…→d27 or d8→d10→…→d26→d9→ …→d26 The two are similar, where di represents all combinations of 5 slots and i. In fact, for an array, the sum of its digits is the same, so it is obviously impossible for it to be mutually exclusive. For other cases, you can use the following method to identify: use the Numpy third-party library in Python to perform list vectorization operations, subtract two lists, and then sum them. If the absolute value is 1, the two may be mutually exclusive; otherwise, they cannot be mutually exclusive. , The array di with the number sum as i, and the other set of data as d_i^', then the following conclusions: d_i^'∩d_((i+1))≠∅ d_i^'∩d_((i))=∅ d_i^'∩d_((i+j))=∅ It can be seen that: d_26^'∩d_27≠∅ d_8^'∩d_27≠∅ And the numbers and all even or all odd arrays must not be separated from each other, so The above design meets the requirements.
  3. Customers complained about the quantitative measurement of the dissatisfaction degree of their customers when they were randomly packed. In quantitative expression, we think that it can be expressed by the following quantities: A: The number of mutually unlocked devices in a certain amount; B: The probability of mutual opening in a certain amount; C: Use computer simulation to simulate the random packing process, and randomly select points. Calculation.

Modeling and solving

1. Using the idea of ​​elimination method for the number of locks, through the Python language, the locks that do not meet the requirements are gradually eliminated. There are 5880 locks, each of which is 60, and 98 boxes can be loaded. The code is as follows:

lists = [1,2,3,4,5,6]
list_alls = []
for list_1 in lists:
    for list_2 in lists:
        for list_3 in lists:
            for list_4 in lists:
                for list_5 in lists:
                    list_alls.append([list_1,list_2,list_3,list_4,list_5])
print(len(list_alls))
list_deletes_1 = []
for list_all in list_alls:
    counts = list(set(list_all))
    if len(counts) <= 2:
        pass
    else:
        list_deletes_1.append(list_all)
print(len(list_deletes_1))
list_deletes_2 = []
for list_all_1 in list_deletes_1:
    if abs(list_all_1[0]-list_all_1[1]) == 5:
        pass
    elif abs(list_all_1[1]-list_all_1[2]) == 5:
        pass
    elif abs(list_all_1[2]-list_all_1[3]) == 5:
        pass
    elif abs(list_all_1[3]-list_all_1[4]) == 5:
        pass
    else:
        list_deletes_2.append(list_all_1)
print(len(list_deletes_2))

2. The packing scheme design first proves that d9→d11→…→d27→d 8→d10→d12→…→d27 has no mutual open phenomenon. Suppose a certain list is [a,b,c,d,e] (a+b+c+d+e=i is an odd number), then (a±1)bcde, a(b±1)cde, ab( c±1)de, abc(d±1)e, abcd(e±1), when it contains the unqualified items whose adjacent difference is 5 or the bit is 0, you can know a+b+c+d +e±1=i(±1) then it is an even number, which cannot be the same as any element (combination) in d9→d27, similar to d8→d10→…→d26. It can be proved that 49 boxes are the maximum number of boxes without mutual opening, that is, the odd-even boxing scheme. 3. Customers complained that the quantitative measurement uses Python to calculate all possible open pairs as 22778, and the average open coefficient α=0.001317. For one box, the number of open pairs is about 2.33, and the number of two boxes is about 9.42. The code is as follows:

import random
i = 0
xiangjian_list = []
hukai_counts = []
list_randoms = random.sample(list_deletes_2,60)
for list_randoms_1 in list_randoms:
    i = i+1
    for list_randoms_2 in list_randoms[i:]:
        list_1 = [list_randoms_1[0]-list_randoms_2[0],list_randoms_1[1]-list_randoms_2[1],list_randoms_1[2]-list_randoms_2[2],list_randoms_1[3]-list_randoms_2[3],list_2 list_randoms_1[4] 4]]
        xiangjian_list.append(list_1)
for list_2 in xiangjian_list:
    if (list_2.count(0) == 4):
        if (list_2.count(1) == 1 | list_2.count(1) == 1):
            hukai_counts.append('a')
print(len(hukai_counts))
Reference: https://cloud.tencent.com/developer/article/1155568 Python data analysis of lock packing problem problem restatement problem analysis modeling and solution-cloud + community-tencent cloud