Math python question

[Phro0244]

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

 

[menator01]

The question is vague. Can you give an example?

 

[WhiteCube]

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.

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

 

[Phro0244]

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

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?

 

[Phro0244]

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.

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?

 

[WhiteCube]

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.

 

[Phro0244]

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

 

[WhiteCube]

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.

 

[WhiteCube]

No, that's not right.
Back to the drawing board.

 

[thugbunny]

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:

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))

 

[Phro0244]

Thank you for all the good answers!