从数组列表中找到唯一代表(元素)的列表 [英] Find a list of unique representatives (elements) from a list of arrays

问题描述

我有一个由n数组组成的列表(或数组).每个数组都携带一个从0到n-1的整数的任意子集(数字在数组中不重复). n=3的示例是:

I have a list(or array) consist of n arrays. Each array carries an arbitrary subset of integers from 0 to n-1 (numbers are not repeated within an array). An example for n=3 is:

l = [np.array([0, 1]), np.array([0]), np.array([1, 2])]

我想从每个数组中选择一个单一的数字作为其代表，以便没有两个数组具有相同的代表，并以与数组相同的顺序列出它们.换句话说，为数组选择的数字必须唯一，并且代表的整个集合将是数字0到n-1的排列.对于上面的列表，它将唯一地是:

I want to pick one single number from each array as its representative, such that no two arrays have the same representative and make a list of them in the same order as arrays. In other words, the numbers picked for arrays must be unique and the whole set of representatives, will be a permutation of numbers 0 to n-1. For above list, it would uniquely be:

representatives = [1, 0, 2]

可以保证我们的名单中存在这样的代表名单，但是我们如何找到他们.如果存在多个可能的代表列表，则可以随机选择任何一个代表.

There is a guarantee that such list of representatives exist for our list, but how do we find them. In case, there are more than one possible list of representatives, any one of them can be randomly selected.

推荐答案

这是您要寻找的吗?

def pick_one(a, index, buffer, visited):
    if index == len(a):
        return True
    for item in a[index]:
        if item not in visited:
            buffer.append(item)
            visited.add(item)
            if pick_one(a, index + 1, buffer, visited):
                return True
            buffer.pop()
            visited.remove(item)
    return False


a = [[0, 1], [0], [1, 2]]
buffer = []
pick_one(a, 0, buffer, set())
print(buffer)

输出:

[1, 0, 2]

这篇关于从数组列表中找到唯一代表(元素)的列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！