【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 = 1for (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 = 1for (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))