Как мне выполнять итерацию при реализации алгоритма X, пока не будут созданы и показаны все возможные решения? ⇐ Python

[Anonymous]

Я пытаюсь использовать алгоритм X для решения точной задачи покрытия данной матрицы. Подробности алгоритма X, который я собираюсь реализовать. Сначала мы находим столбец c с наименьшим количеством единиц, выбираем строку r, содержащую 1 в столбце c, добавляем строку r в L, удаляем строки, которые конфликтуют со строкой r, исключаем столбцы, которые конфликтуют. со строкой r удалите строку r и выведите оставшуюся матрицу.
Я жестко запрограммировал матрицу, чтобы упростить тестирование. При отладке мои функции работают индивидуально, но моя логика отключена. Он может выводить только один ответ вместо каждого решения и сохраняет неправильные строки при проходе по матрице. Одним из решений для данной матрицы является L = {2, 4, 6}, но я получаю только {0, 4, 2}.
def check_zeros(matrix):
for i in range(len(matrix[0])): # iterate through each column, size of row denotes each column index
if all(matrix[j] == 0 for j in range(len(matrix))): # if all entries in a column are 0
return True # indicates no solution for this matrix
return False

def check_ones(matrix):
for i in range(len(matrix)): # iterate through each row
if all(matrix): # if the entire row consists of 1s
return i # return the index of the row
return False # returns false if none of the rows contain only 1's

def pick_columns(matrix): saves the index of columns with 1's in ascending
columns_with_ones = []

for j in range(len(matrix[0])):
num_ones = sum(matrix[j] for i in range(len(matrix)))
if num_ones > 0:
columns_with_ones.append((j, num_ones))

columns_with_ones.sort(key=lambda x: x[1])
sorted_columns = [col[0] for col in columns_with_ones]
return sorted_columns

def pick_rows(matrix, column):
return [i for i in range(len(matrix)) if matrix[column] == 1]

def remove_column(matrix, column):
return [[row[j] for j in range(len(row)) if j != column] for row in matrix]

def remove_rows(matrix, row):
new_matrix = []
for i, r in enumerate(matrix):
if i == row:
continue # skip the selected row
# Append rows that do not conflict with the selected row
if not any(matrix[row][j] == 1 and r[j] == 1 for j in range(len(matrix[0]))):
new_matrix.append(r)
return new_matrix

def remove_columns(matrix, row):
columns_to_remove = [j for j in range(len(matrix[0])) if matrix[row][j] == 1]
new_matrix = [list(r) for r in matrix] #create a copy to avoid modifying the original
for col in reversed(columns_to_remove):
new_matrix = remove_column(new_matrix, col)
return new_matrix

def exact_cover_problem():
arr = []
col = 0

while True:
inp = input("Input matrix by each row, press 'y' to stop (example 1010): \n")
if inp.lower() != "y":
arr.append(inp)
col = max(col, len(inp))
else:
break

matrix = [list(map(int, s.ljust(col, '0'))) for s in arr]
print("\nExact Cover Problem:")
for row in matrix:
print(row)

return matrix

def algorithm_x(matrix, L=None):
if L is None:
L = []

# Check for columns without 1's
if check_zeros(matrix):
return None # No solution

# Check if there's a row with all 1's
if (row := check_ones(matrix)) is not False:
return L + [row]

columns = pick_columns(matrix)
if not columns: # If no valid column found, return None
return None

column = columns[0]

rows = pick_rows(matrix, column)

for row in rows:
new_matrix = remove_rows(matrix, row)
new_matrix = remove_columns(new_matrix, row)

result = algorithm_x(new_matrix, L + [row])
if result:
return result

return None

# Main execution
matrix = [
[1, 1, 0, 0, 1, 0, 0],
[1, 1, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 1, 1, 0],
[0, 0, 0, 1, 0, 1, 1],
[0, 0, 1, 1, 1, 0, 1],
[0, 0, 1, 0, 1, 0, 0],
]
result = algorithm_x(matrix)

# Display the results
# print("\nSolutions using Knuth's Algorithm X:")
# if result:
# print("Rows selected (L):", result)
# else:
# print("No exact cover solution found ")

print("\nAll possible solutions using Knuth's Algorithm X:")
if result:
print(f"Solution: {result}")
else:
print("No exact cover solution found ")


Подробнее здесь: https://stackoverflow.com/questions/791 ... utions-are