How to select any value from a list with row and column?

there is a list with items:

items = list(range(4))

and there is a list with rows i and columns j

and the constraint x(i,j) != x(j,i).

e.g.,

values = [
    [0, 10, 5, 4], 
    [8, 0, 9, 11], 
    [8, 15, 0, 8], 
    [7, 11, 13, 0],
]

e.g., how to select value x(2,3)=9 from the list?

To proceed my task i need to select values x[i,j] or x[j,i] with a loop like:

for i in items:
   for j in items:
      --> select from values

.

(be aware: please use itertools and math only.)

Thank you.

CodePudding user response：

Let us assume that x[i,j] = a(i) and x[j,i] = b(j).

When we select a value from the first list it is used as the target of the second list. We can do that as follows:

for i in items:
    for j in items:
        if b(j) == a(i): break # no need to search further on this i-loop

There is an alternative solution that is harder to understand but faster: we can use itertools.permutations() to generate all combinations of row and column indices and check for b(j) == a(i) when we construct the i-loop.

The following implementation is based on the permutations from itertools, but the inner loop can be implemented with any other method that you prefer:

def solve(values):
    items = list(range(len(values)))
    for i, j in itertools.permutations(items, 2):
        if values[i][j] == values[j][i]: break
    else: return False # no need to search further on this i-loop

    # otherwise we have to return True as it is a solution. 
    # Backtracking: We can remove the x[i,j] or x[j,i] from the problem. 
    # We need to remove the x[i,j] because we already have a value for x[j,i]. 
    # So we can remove both from the problem by removing all rows/columns that contain either of those two values. 

    removed = set() # a collection that stores element that are removed from items

    if i not in removed:
        del values[i]         # If a value of i is not already removed from items, remove i and its associated value from items. 
        removed.add(i)        # add it to the collection of removed elements

    if j not in removed:       # The same procedure is repeated for j and row/column removal. 
        del values[j]         # If you don't understand why we want to do that please consult with Knuth's paper again (PDF). 
        removed.add(j)

    return solve(values)      # Backtracking: Try to solve the problem again by recursively calling this function. 

CodePudding user response：

This is my solution:

for i in items:
    for j in items:
        list = {(i, j): values[i][j] for i, j in combinations(items, 2)}