Anti-sum drawers

[Paul_Maillet]

Hello ! I need someone to quickly run a program that takes time...
I am French and I am in high school, I'm researching anti-sum drawers, i.e., drawers whose sum of two elements does not give the value of another element in the same drawer.
(a + b !=c, a b and c in the same drawer)
In this program, there are three drawers, it tests all the possible combinations which make it possible to go up to a given number (n) and checks at the same time if these are anti-sums. This program allows you to prove which is the best combination for three drawers.
By observing the time the program took for small numbers, I deduced that the program was exponentially complex, and therefore it would take several days for it to find the solution.
(7 days for n = 23 with my computer (not very powerful) according to my calculations )
That's why I will need someone to test with a more powerful computer to have a result before
the day of the mathematics congress (23 march), which would therefore be faster the program with the value 23 then 24.
The program should return several solutions for 23 and nothing for 24, which would prove that 23 is the maximum. It would help me a lot!
I am attaching the program, the function to run is combi(n):

import time
def gen_combinations(numbers, n):
    if n == 0:
        yield []
    else:
        for i in range(3):
            for sub_comb in gen_combinations(numbers, n-1):
                yield [i] + sub_comb

def combi(n):
    start_time = time.time() # démarrer le chronomètre
    numbers = list(range(1, n+1))
    combinaisons = []
    for combinaison in gen_combinations(numbers, n):
        tiroir1 = []
        tiroir2 = []
        tiroir3 = []
        for i in range(n):
            if combinaison[i] == 0:
                tiroir1.append(numbers[i])
            elif combinaison[i] == 1:
                tiroir2.append(numbers[i])
            else:
                tiroir3.append(numbers[i])
        if est_anti_somme(tiroir1) and est_anti_somme(tiroir2) and est_anti_somme(tiroir3):
            combinaisons.append((tuple(tiroir1), tuple(tiroir2), tuple(tiroir3)))

    if combinaisons == []:
        print("Il n'y a pas de solutions allant jusqu'à", n)
    else :
        print("il y a", len(combinaisons), 'possibilités')
    # Convertir les tuples en sous-listes
    result = [[list(tiroir1), list(tiroir2), list(tiroir3)] for (tiroir1, tiroir2, tiroir3) in combinaisons]
    end_time = time.time() # arrêter le chronomètre
    print(f"Temps d'exécution : {end_time - start_time:.4f} secondes")
    return result

def est_anti_somme(tab):
    '''
    Renvoie True si on NE peut PAS obtenir un élément du tableau en ajoutant deux élements
    de ce tableau et False sinon
    : param tab (list) tableau d'entiers
    : return (bool)
    >>> est_anti_somme([1, 2, 3])
    False
    >>> est_anti_somme([1, 2, 4, 5])
    False
    >>> est_anti_somme([2, 3, 7, 11])
    True
    >>> est_anti_somme([])
    True
    >>> est_anti_somme([0, 0, 0, 0])
    False
    >>> est_anti_somme([0])
    True
    '''
    if len(tab) < 2:
        return True
    return all(tab[i]+tab[j] not in tab for i in range(len(tab)) for j in range(i+1, len(tab)))

    return result

[Gribouillis]

Hello Paul and welcome to python-forum.io !

My computer would also take an infinite time to run your program with n=23.

However, faster algorithms are possible. Here is my attempt on this problem, which runs in less than 0.1 second for n=23

def combinaisons(n):
    if n == 0:
        yield [(0, 0), (0, 0), (0, 0)]
    else:
        b = 1 << n
        for tiroirs in combinaisons(n-1):
            for i, (t, som) in enumerate(tiroirs):
                if not (som & b):
                    c = list(tiroirs)
                    c[i] = (t | b, som | (t << n))
                    yield c

def tiroir_as_list(t):
    x = bin(t[0])[2:][::-1]
    return [i for i, b in enumerate(x) if b == '1']

def combin_as_list(c):
    return [tiroir_as_list(t) for t in c]

if __name__ == '__main__':
    for c in combinaisons(23):
        print(combin_as_list(c))

λ time python paillasse/pf/tiroir2.py
[[1, 2, 4, 8, 11, 16, 22], [3, 5, 6, 7, 19, 21, 23], [9, 10, 12, 13, 14, 15, 17, 18, 20]]
[[1, 2, 4, 8, 11, 17, 22], [3, 5, 6, 7, 19, 21, 23], [9, 10, 12, 13, 14, 15, 16, 18, 20]]
[[1, 2, 4, 8, 11, 22], [3, 5, 6, 7, 19, 21, 23], [9, 10, 12, 13, 14, 15, 16, 17, 18, 20]]
[[1, 2, 4, 8, 11, 16, 22], [9, 10, 12, 13, 14, 15, 17, 18, 20], [3, 5, 6, 7, 19, 21, 23]]
[[1, 2, 4, 8, 11, 17, 22], [9, 10, 12, 13, 14, 15, 16, 18, 20], [3, 5, 6, 7, 19, 21, 23]]
[[1, 2, 4, 8, 11, 22], [9, 10, 12, 13, 14, 15, 16, 17, 18, 20], [3, 5, 6, 7, 19, 21, 23]]
[[3, 5, 6, 7, 19, 21, 23], [1, 2, 4, 8, 11, 16, 22], [9, 10, 12, 13, 14, 15, 17, 18, 20]]
[[3, 5, 6, 7, 19, 21, 23], [1, 2, 4, 8, 11, 17, 22], [9, 10, 12, 13, 14, 15, 16, 18, 20]]
[[3, 5, 6, 7, 19, 21, 23], [1, 2, 4, 8, 11, 22], [9, 10, 12, 13, 14, 15, 16, 17, 18, 20]]
[[9, 10, 12, 13, 14, 15, 16, 17, 18, 20], [1, 2, 4, 8, 11, 22], [3, 5, 6, 7, 19, 21, 23]]
[[9, 10, 12, 13, 14, 15, 16, 18, 20], [1, 2, 4, 8, 11, 17, 22], [3, 5, 6, 7, 19, 21, 23]]
[[9, 10, 12, 13, 14, 15, 17, 18, 20], [1, 2, 4, 8, 11, 16, 22], [3, 5, 6, 7, 19, 21, 23]]
[[3, 5, 6, 7, 19, 21, 23], [9, 10, 12, 13, 14, 15, 16, 17, 18, 20], [1, 2, 4, 8, 11, 22]]
[[3, 5, 6, 7, 19, 21, 23], [9, 10, 12, 13, 14, 15, 16, 18, 20], [1, 2, 4, 8, 11, 17, 22]]
[[3, 5, 6, 7, 19, 21, 23], [9, 10, 12, 13, 14, 15, 17, 18, 20], [1, 2, 4, 8, 11, 16, 22]]
[[9, 10, 12, 13, 14, 15, 16, 17, 18, 20], [3, 5, 6, 7, 19, 21, 23], [1, 2, 4, 8, 11, 22]]
[[9, 10, 12, 13, 14, 15, 16, 18, 20], [3, 5, 6, 7, 19, 21, 23], [1, 2, 4, 8, 11, 17, 22]]
[[9, 10, 12, 13, 14, 15, 17, 18, 20], [3, 5, 6, 7, 19, 21, 23], [1, 2, 4, 8, 11, 16, 22]]

real    0m0,097s
user    0m0,082s
sys     0m0,016s

My program is lacking tests to ensure that all the results are correct and that it computes every combination.

In my algorithm, the contents of a drawer is represented by an integer, for example the integer 2374664 has binary representation

>>> n = 2374664
>>> bin(n)
'0b1001000011110000001000'

In this number, the bits set (starting from the right) are 3, 10, 11, 12, 13, 18, 21, so this number can be used to represent the list [3, 10, 11, 12, 13, 18, 21].

All the possible sums of all the numbers contained in the drawer are also stored as an integer, so that a drawer is implemented as a pair of integers (x, s)

[Paul_Maillet]

Your program is working way more faster ! I looked at the result and I saw exactly the right amount of combinations,
I would never have thought of using your method! Thank you so much !!

[Gribouillis]

I would never have thought of using your method!

After a few years of programming computers, you would start thinking of such methods. The moral of the story is that in most cases, when a program is slow, the solution is not to find a better computer. There is usually plenty of room for a faster implementation once the first version of a program has been written.

[Paul_Maillet]

Hello again, now that I have the combinations, it would be great if I had a tree to show all the possible paths but I don't really know how to make a program that does that from a txt
I already did it if for 2 drawers (in the program we had 3) in LaTex :

Drawers with no sum : (Starting here from one in the first drawer then we place 2 in the first drawer or the second drawer)


Every possible combination(even the ones that doesn't work, 2^n combinations):


Inside the text below, there is at first the root, then its children and then their children... Every combination is a node.
Does someone knows how to interpret the text from python and make a tree from this ?
https://drive.google.com/file/d/1g7Dlsm4...sp=sharing

[Gribouillis]

If you are allowed to use external modules, you could do this with networkx for example, but your tree has tenth of thousands of nodes, so you need to prune it somehow if you want to see anything.

[Paul_Maillet]

If you are allowed to use external modules, you could do this with networkx for example, but your tree has tenth of thousands of nodes, so you need to prune it somehow if you want to see anything.

Yeah, it is allowed to use external modules, I t might be possible to cut some combinations, like assuming the number one is in the first drawer, it divides the number of possibility by 3. And also do some changes like the combination [[1, 2],[],[]] is the same as [[],[1, 2],[]] or [[],[],[1, 2]]...