# 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

Last edited:

#### 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.

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

#### 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
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:

#### 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.

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``````
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:
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:

# 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]:
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!