javascript - 从数组数组中挑选一个唯一的集合

Question

我之前试图问一个更复杂的问题，但我无法很好地解释它，所以我再次尝试使用一个简化的用例。
我将有一个数组，如下所示

var allData = [[1,2,3,4,5],[1,2,3,4,5],[1,2,3,4,5],[1,2,3,4,5],[1,2,3,4,5]]

我需要从每个数组中选择 1 个元素，以便获得像 [2,4,1,3,5] 这样的唯一集合，在这种情况下很容易做到，因为每个数组都有所有值。然而，这种情况很少发生。相反，我可能有

var allData = [[1,2,4],[1,2],[1,2],[2,4,5],[1,2,3,5]]

在这种情况下，我无法从第一个数组中选择 1 或 2，因为这会阻止第 2 和第 3 具有唯一组合。所以像 [4,2,1,5,3] 或 [4,1,2,5,3] 这样的组合将是这种组合的唯一两个可能的答案。
我看到这样做的唯一方法是遍历每个组合，但这些组合会变得相当大，所以这似乎不合理，因为这种情况是实时发生的。将至少有 7 个阵列，可能有 14 个，并且很可能有 31 个，因此通过每个组合将相当粗糙。
第二部分是如果有某种方法可以“知道”你有最好的选择。假设如果有某种方式我会知道拥有一个副本是我最好的情况。即使遇到 1 重复解决方案我必须强制使用它，我也会知道停止。
一种简单的方法是从元素的数量中减去可能的选择数量，但这仅在最简单的情况下才是正确的答案。是否有某种类型的库或任何东西可以帮助解决这些类型的问题？这有点超出我的数学能力。
这是我尝试过的方法，但对于较大的集合来说太慢并且可能会失败。它有时适用于我提出的第二种情况，但只能靠运气

const allData = [[1,2,4],[1,2],[1,2],[2,4,5],[1,2,3,5]]
var selectedData = []
for (var i in allData){
  console.log("length",allData[i].length)
  var j = 0
  while(j < allData[i].length){
    console.log("chekcing",allData[i][j])
    if (selectedData.includes(allData[i][j])){
      console.log("removing item")
      allData[i].splice(j,1)
    }
    else{j++}
  }
  var uniqueIds = Object.keys(allData[i])
  console.log(uniqueIds)
  var randId = Math.floor(Math.random() * uniqueIds.length)
  console.log(randId)
  selectedData.push(allData[i][randId])  
  console.log("selectedData",selectedData)
}

Answer 1

您可以从一个相当简单的回溯算法开始:

function pick(bins, n = 0, res = {}) {
    if (n === bins.length) {
        return res
    }

    for (let x of bins[n]) {
        if (!res[x]) {
            res[x] = n + 1
            let found = pick(bins, n + 1, res)
            if (found)
                return found
            res[x] = 0
        }
    }
}

//

let a = [[1, 2, 4], [1, 2], [1, 2], [2, 4, 5], [1, 2, 3, 4]]
console.log(pick(a))

这将返回一个映射 item => bin index + 1 ，如果需要，很容易转换回数组。
这应该在 N < 10 时表现得相对较好，对于更多/更大的 bin，您可以考虑一些优化，例如，通过将 bin 从最小到最长排序来避免最坏的情况，或者，根据元素的性质，将 bin 表示为位掩码。