【ES6】使用Set和Map进行全组合判断

判断数据集是否为全组合关系

例如下列表格，字段1包含（甲、乙）值，字段2包含（a、b）值，字段3包含（1、2、3）值，每种组合情况都可以在数据集的行记录中找到有且仅有的一条。

要求函数输入以下格式数据，输出布尔值。

const inputData = [
	{ "字段1": "甲", "字段2": "a", "字段3": 1 },
	{ "字段1": "甲", "字段2": "a", "字段3": 2 },
	{ "字段1": "甲", "字段2": "a", "字段3": 3 },
	{ "字段1": "甲", "字段2": "b", "字段3": 1 },
	{ "字段1": "甲", "字段2": "b", "字段3": 2 },
	{ "字段1": "甲", "字段2": "b", "字段3": 3 },
	{ "字段1": "乙", "字段2": "a", "字段3": 1 },
	{ "字段1": "乙", "字段2": "a", "字段3": 2 },
	{ "字段1": "乙", "字段2": "a", "字段3": 3 },
	{ "字段1": "乙", "字段2": "b", "字段3": 1 },
	{ "字段1": "乙", "字段2": "b", "字段3": 2 },
	{ "字段1": "乙", "字段2": "b", "字段3": 3 },
]

实现

1.遍历inputData并罗列出每个字段对应的全部可能值：

const inputData = [
  { "字段1": "甲", "字段2": "a", "字段3": 1 },
  { "字段1": "甲", "字段2": "a", "字段3": 2 },
  { "字段1": "甲", "字段2": "a", "字段3": 3 },
  { "字段1": "甲", "字段2": "b", "字段3": 1 },
  { "字段1": "甲", "字段2": "b", "字段3": 2 },
  { "字段1": "甲", "字段2": "b", "字段3": 3 },
  { "字段1": "乙", "字段2": "a", "字段3": 1 },
  { "字段1": "乙", "字段2": "a", "字段3": 2 },
  { "字段1": "乙", "字段2": "a", "字段3": 3 },
  { "字段1": "乙", "字段2": "b", "字段3": 1 },
  { "字段1": "乙", "字段2": "b", "字段3": 2 },
  { "字段1": "乙", "字段2": "b", "字段3": 3 },
]

function isFullCombination(data) {
  if (data.length === 0) {
    return false
  }

  const fieldMap = new Map() // 字段映射对象
  const keys = Object.keys(data[0]) // 获取数据集字段名

  for (const item of data) {
    for (const key of keys) {
      const value = item[key]
      let valueSet = fieldMap.get(key) // 尝试获取Map中字段对应的值集合
      if (!valueSet) {
        valueSet = new Set() // 使用Set实现去重
        fieldMap.set(key, valueSet)
      }
      valueSet.add(value)
    }
  }

  console.log(fieldMap);
}

console.log(isFullCombination(inputData));

Map(3) {
  '字段1' => Set(2) { '甲', '乙' },
  '字段2' => Set(2) { 'a', 'b' },
  '字段3' => Set(3) { 1, 2, 3 }
}

2.那么全组合情况下，inputData数组的长度应为 2*2*3，也就是12，对长度进行判断：

function isFullCombination(data) {
  if (data.length === 0) {
    return false
  }

  const fieldMap = new Map()
  const keys = Object.keys(data[0]) 

  for (const item of data) {
    for (const key of keys) {
      const value = item[key]
      let valueSet = fieldMap.get(key) 
      if (!valueSet) {
        valueSet = new Set() 
        fieldMap.set(key, valueSet)
      }
      valueSet.add(value)
    }
  }
  
  const length = [...fieldMap].reduce((s, [, v]) => (s *= v.size), 1)
  return length === data.length // 对比length
}

3.除了length还需要考虑元素是否重复，如果对inputData进行去重处理，会提高时间复杂度，所以在已有的循环中顺便进行是否重复的判断即可。将所有值拼接为字符串并存储到集合中，对比字符串是否相同。

：拼接后的字符存储到集合中，因为需要判断集合中是否已有重复的字符串，所以使用Set存储，因为Set.has时间复杂度为O(1)，而Array判断时间复杂度为O(n)。

function isFullCombination(data) {
  if (data.length === 0) {
    return false
  }

  const fieldMap = new Map() 
  const keys = Object.keys(data[0]) 

  const combinationSet = new Set() // 组合情况集合
  for (const item of data) {
    let combination = ""
    for (const key of keys) {
      const value = item[key]
      let valueSet = fieldMap.get(key) 
      if (!valueSet) {
        valueSet = new Set() 
        fieldMap.set(key, valueSet)
      }
      valueSet.add(value)
      combination += value
    }
    if (combinationSet.has(combination)) {
      return false // 如果重复，则说明不是全组合
    }
    combinationSet.add(combination) // 如果不存在，则添加到集合中
  }
  console.log(combinationSet)

  const length = [...fieldMap].reduce((s, [, v]) => (s *= v.size), 1)
  return length === data.length
}

4.但是还存在问题，那就是字段值重复，如下面这个inputData：

const inputData = [
  { a: "-", b: "-" },
  { a: "-", b: "--" },
  { a: "--", b: "-" },
  { a: "--", b: "--" },
]

目前无法判断，需要在存入映射对象时手动将值存为唯一值，这里通过自增的n作为唯一标识，然后使用每个字段对应的唯一标识拼接字符串。

function isFullCombination(data) {
  if (data.length === 0) {
    return false
  }

  const fieldMap = new Map() 
  const keys = Object.keys(data[0]) 
  const combinationSet = new Set()
  const valueMap = new Map() // 记录每个字段的值集合
  let n = 1

  for (const item of data) {
    let combination = ""
    for (const key of keys) {
      const value = item[key]
      let valueSet = fieldMap.get(key)
      if (!valueSet) {
        valueSet = new Set() 
        fieldMap.set(key, valueSet)
      }
      valueSet.add(value)

      let num = valueMap.get(value) // 尝试获取Map中字段对应的值
      if (!num) {
        num = n++
        valueMap.set(value, num) 
      }
      combination += num+''
    }
    console.log(valueMap)

    if (combinationSet.has(combination)) {
      return false 
    }
    combinationSet.add(combination) 
  }

  const length = [...fieldMap].reduce((s, [, v]) => (s *= v.size), 1)
  return length === data.length
}

整体实现代码

const inputData = [
  { 字段1: "甲", 字段2: "a", 字段3: 1 },
  { 字段1: "甲", 字段2: "a", 字段3: 2 },
  { 字段1: "甲", 字段2: "a", 字段3: 3 },
  { 字段1: "甲", 字段2: "b", 字段3: 1 },
  { 字段1: "甲", 字段2: "b", 字段3: 2 },
  { 字段1: "甲", 字段2: "b", 字段3: 3 },
  { 字段1: "乙", 字段2: "a", 字段3: 1 },
  { 字段1: "乙", 字段2: "a", 字段3: 2 },
  { 字段1: "乙", 字段2: "a", 字段3: 3 },
  { 字段1: "乙", 字段2: "b", 字段3: 1 },
  { 字段1: "乙", 字段2: "b", 字段3: 2 },
  { 字段1: "乙", 字段2: "b", 字段3: 3 },
]

// const inputData = [
//   { a: "-", b: "-" },
//   { a: "-", b: "--" },
//   { a: "--", b: "-" },
//   { a: "--", b: "--" },
// ]

function isFullCombination(data) {
  if (data.length === 0) {
    return false
  }

  const fieldMap = new Map() // 字段映射对象
  const keys = Object.keys(data[0]) // 获取数据集字段名
  const combinationSet = new Set() // 组合情况集合
  const valueMap = new Map() // 记录每个字段的值集合
  let n = 1

  for (const item of data) {
    let combination = ""
    for (const key of keys) {
      const value = item[key]
      let valueSet = fieldMap.get(key) // 尝试获取Map中字段对应的值集合
      if (!valueSet) {
        valueSet = new Set() // 使用Set实现去重
        fieldMap.set(key, valueSet)
      }
      valueSet.add(value)

      let num = valueMap.get(value) // 尝试获取Map中字段对应的值
      if (!num) {
        num = n++
        valueMap.set(value, num)
      }
      combination += num + ""
    }
    console.log(combination)

    if (combinationSet.has(combination)) {
      return false // 如果重复，则说明不是全组合
    }
    combinationSet.add(combination) // 如果不存在，则添加到集合中
  }

  const length = [...fieldMap].reduce((s, [, v]) => (s *= v.size), 1)
  return length === data.length
}

console.log(isFullCombination(inputData))