🔒 Seeking Efficient Enumeration Strategies for Graph Partitioning

[uncut cave]

@lofty fossil

Python help channel opened

Remember to:

• Ask your Python question, not if you can ask or if there's an expert who can help.
• Show a code sample as text (rather than a screenshot) and the error message, if you've got one.
• Explain what you expect to happen and what actually happens.

:warning: Do not pip install anything that isn't related to your question, especially if asked to over DMs.

Closes after a period of inactivity, or when you send !close.

[lofty fossil]

For my initial approach, I am focusing on the explicit enumeration ("generate and test") method to find the optimal partitioning. The project's requirements include to find the optimal solution for small graphs (25 vertices)

To approach this, I've developed a function that explicitly enumerates the entire brute search space. However, this method has proven to be less than ideal. For instance, when setting n=16 (vertices) and p=5 (classes), generating all possible partitions already takes more than 10 minutes. Given that I need to find the optimal solution for graphs up to 25 vertices, I cannot begin to imagine the time it would take for even larger instances. This has led me to conclude that before evaluating the current solution from my brute search space, I must first find a way to effectively reduce the possibilities within my search space.

How can I pre-reduce the enumeration process's search space effectively? Are there known strategies or criteria that can help eliminate non-viable partitions early on?

from itertools import product
import time

def generer_vecteurs(n, p):
    for vecteur in product(range(1, p + 1), repeat=n):
        pass 


n = 15  
p = 5   

start_time = time.time()
generer_vecteurs(n, p)
end_time = time.time()

execution_time = end_time - start_time
execution_time

[uncut cave]

@lofty fossil

Python help channel closed

This help channel has been closed and it's no longer possible to send messages here. If your question wasn't answered, feel free to create a new post in #1035199133436354600. To maximize your chances of getting a response, check out this guide on asking good questions.