Math python question

Joined
Mar 31, 2023
Messages
95
Reaction score
8
Hello, I'm new to this forum and I have a question. for those who are interested.
If i have a list of number ex: N=[1,2,3,4] and that I also have a list of numbers that cannot be together ex: P=[(1,2),(2,3),(3,4)] is it possible to make a cheap algorithm that won't test all the possible combinations to find a combination that works?

thanks for any response

Phil
 
Last edited:
Joined
Sep 21, 2022
Messages
126
Reaction score
16
An interesting problem. Thanks for that.

If you want to select r numbers, the common sense approach is, every iteration, choose the number that has the least amount of restrictions.

I think of it as a graph, so I can easily test cases on paper.

A number is a vertex.

A "numbers that cannot be together" is an edge connecting two vertices.

The degree is the number of edges at a vertex.

When you gain one number for your combination, you lose the adjacent numbers.

conjecture: The common sense approach will produce the maximum possible combination.

I can not prove or disprove the conjecture now. This kind of problem takes me weeks.

Code:
pseudocode: select r numbers

count = 0
combination = []
WHILE count < r AND NOT(graph is empty)
  x = any vertex with the lowest degree
  count += 1
  append x's number to combination
  delete x and all vertices adjacent to x

IF count < r
  r was impossible
 
Joined
Mar 31, 2023
Messages
95
Reaction score
8
The question is vague. Can you give an example?
Yes,
so here we have a program that tests all possible combinations and gives you the possible conbinations
Python:
set = []

N = [1,2,3,4]

n = len(N)

for i in range(0,len(N)-1):

    n-=1

    E = N[i]

    for i in range(-n,0):

        X = (E,N[i])

        set .append(X)

Ep = [(1,2),(2,3),(1,4)]

for i in range(len(Ep)):

    if Ep[i] in set :

        set .remove(Ep[i])

print(set)

My question is it possible to arrive at the same result but without testing all the possibilities?
 
Last edited:
Joined
Mar 31, 2023
Messages
95
Reaction score
8
An interesting problem. Thanks for that.

If you want to select r numbers, the common sense approach is, every iteration, choose the number that has the least amount of restrictions.

I think of it as a graph, so I can easily test cases on paper.

A number is a vertex.

A "numbers that cannot be together" is an edge connecting two vertices.

The degree is the number of edges at a vertex.

When you gain one number for your combination, you lose the adjacent numbers.

conjecture: The common sense approach will produce the maximum possible combination.

I can not prove or disprove the conjecture now. This kind of problem takes me weeks.

Code:
pseudocode: select r numbers

count = 0
combination = []
WHILE count < r AND NOT(graph is empty)
  x = any vertex with the lowest degree
  count += 1
  append x's number to combination
  delete x and all vertices adjacent to x

IF count < r
  r was impossible
Thank you for your reply!
But...
How much iteration will it need?
And how to represent edge and vertices in python?
 
Joined
Sep 21, 2022
Messages
126
Reaction score
16
I am assuming that P is always a list of number "pairs", and not a list of unwanted combinations. That assumption makes a difference when the combination size is not 2.

If P is a list of unwanted combinations, my suggestion does not apply.

If the combination size is always 2, there is a very simple way to solve your problem. A two dimensional array.

Iterations, for a combination of size r:

r main loops,

an inner loop thru P to find the number that occurs the least (x),

a second inner loop thru P to delete any number in N that is paired with x.

Roughly r * 2 * len(P) iterations.
 
Joined
Mar 31, 2023
Messages
95
Reaction score
8
I am assuming that P is always a list of number "pairs", and not a list of unwanted combinations. That assumption makes a difference when the combination size is not 2.

If P is a list of unwanted combinations, my suggestion does not apply.

If the combination size is always 2, there is a very simple way to solve your problem. A two dimensional array.

Iterations, for a combination of size r:

r main loops,

an inner loop thru P to find the number that occurs the least (x),

a second inner loop thru P to delete any number in N that is paired with x.

Roughly r * 2 * len(P) iterations.
Yes, indeed its always pairs of 2 thank you for your answer
 
Joined
Sep 21, 2022
Messages
126
Reaction score
16
I'm completely wrong.

There is no simple way to find a valid combination.

Viewing the problem as a graph, with the numbers being vertices, and valid pairs being edges.

The worst-case is finding the largest combination, which is the same as the longest simple path, which is NP-hard.

"Longest path problem" - Wikipedia.
 
Joined
Jan 8, 2023
Messages
27
Reaction score
2
One approach could be to represent the problem as a graph, where the numbers in N are nodes and the pairs in P are edges. Then, you can use a graph traversal algorithm to find a path that visits all the nodes without visiting any of the edges.

Here’s an example implementation in Python:
Python:
from collections import defaultdict

def find_valid_combination(N, P):
    # Create a graph where nodes are numbers in N and edges are pairs in P
    graph = defaultdict(set)
    for a, b in P:
        graph[a].add(b)
        graph[b].add(a)

    # Find a path that visits all nodes without visiting any edges
    path = []
    def dfs(node, visited):
        if len(visited) == len(N):
            return True
        for neighbor in N:
            if neighbor not in visited and neighbor not in graph[node]:
                visited.add(neighbor)
                path.append(neighbor)
                if dfs(neighbor, visited):
                    return True
                visited.remove(neighbor)
                path.pop()
        return False

    for node in N:
        if dfs(node, {node}):
            path.insert(0, node)
            return path
    return None

N = [1, 2, 3, 4]
P = [(1, 2), (2, 3), (3, 4)]
print(find_valid_combination(N, P))
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,820
Messages
2,569,722
Members
45,510
Latest member
ThaliaMaxi

Latest Threads

Top