在多维javascript数组中查找唯一的条目，重要顺序取决于级别

Question

在多维javascript数组中查找所有唯一的一级条目的最优雅的解决方案是什么？只有一条重要规则：条目的顺序仅在第一级很重要，但在第二级不重要

例如，对于以下数组，脚本应该返回4个唯一条目(第一个、第三个、第四个和第五个)：

[
[ [],[22],[1,13,17],[12],[] ], 
[ [],[22],[17,13,1],[12],[] ], 
[ [],[12],[1,13,17],[22],[] ], 
[ [11],[12],[13],[14],[15] ], 
[ [15],[14],[13],[12],[11] ]
]

PS。jQuery也可以使用。

Answer 1

首先，这里有一个可供您使用的JSFiddle：http://jsfiddle.net/missyalyssi/ro8o94nk/

给定一个输入数组，函数findUnique将返回一个数组，该数组包含根据您的定义唯一的项。例如：

[[8]、[1，2，3]、[9]]是[[8]、[3，1,2]、[9]]的副本，但不是[[9]、[3、1,2]、[8]]的副本

我写这篇文章的主要目的是让它易于阅读和理解。

function findUnique(input) {
let found = [];
let uniqueEls = new Set();
let hasDup = true;
for (let element of input) {
hasDup = found.length && 
found.every((el) => {return deepEqualsNaive(el, element)});
if (hasDup) {
uniqueEls.delete(element);
continue;
}
found.push(element);
uniqueEls.add(element);
}
return [...uniqueEls];
}

此函数使用deepEqualsNaive来确定两个数组是否相等。由于javascript中的对象相等意味着数组将指向相同的内存位置，因此我们需要构建自己的函数，以便为我们所称的相等返回true。这里，相等意味着它们具有相同的元素，即使它们不指向相同的内存位置，或者以相同的顺序出现。

为了可读性，我已经递归地编写了这个函数我不知道你在什么上下文中使用这个函数。如果你可以溢出堆栈，那么使用迭代版本。

以下是一些示例输入和我们期望的内容：

deepEqualsNaive([ [],[22],[1,13,17],[12],[] ], [ [],[22],[17,13,1],[12],[] ]) => true
deepEqualsNaive([ [],[22],[17,13,1],[12],[] ], [ [],[12],[1,13,17],[22],[] ]) => false
deepEqualsNaive([ [],[22],[1,13,17],[12],[] ], [ [],22,[17,13,1],[12],[] ]) => false

功能：

function deepEqualsNaive (input, clone) {
if (!Array.isArray(input) || !Array.isArray(clone)) return false;
if (input.length !== clone.length) return false;
var result = 0;
for (let elIdx = 0; elIdx < input.length; elIdx++) {
var tryDeep = true;
if (Array.isArray(input[elIdx])) tryDeep = deepEqualsNaive(input[elIdx], clone[elIdx]);
if (!tryDeep) return false;
result ^= input[elIdx];
result ^= clone[elIdx];
}
return result === 0;
}

Answer 2

如果你不太担心性能，只需要一些有效的东西，你可以使用你提到的恒定深度和字符串表示作为某种"指纹"(类似于Java的hashcode)。

然后使用Set来跟踪以前从未见过的项目，并只添加那些新的项目。

function getUnique(rows) {
let unique = new Set();
let results = [];
for (let row of rows) {
// Fingerprint is the string representation of the row,
// with the inner-level sorted (as order doesn't matter).
// E.g., fingerprint of [ [8], [3, 2, 1], [9] ] is '[[8],[1,2,3],[9]]'
let fingerprint = JSON.stringify(row.map((cells) => {
return cells.concat().sort();  // Use concat to avoid sorting in place.
}));
// If we haven't seen this fingerprint before,
// add to the filter and the results list.
if (!unique.has(fingerprint)) {
unique.add(fingerprint);
results.push(row);
}
}
return results;
}

例如，这将产生。。。

> x = [
... [ [8], [3, 2, 1], [9] ],
... [ [7], [8, 3, 9], [1, 2] ],
... [ [8], [1, 2, 3], [9] ],
... ];
> getUnique(x);
[ [ [ 8 ], [ 3, 2, 1 ], [ 9 ] ],
[ [ 7 ], [ 8, 3, 9 ], [ 1, 2 ] ] ]

显然，如果您的内部值是非基元(对象、数组等)，那么这将失败，但如果您处理的是像您的示例一样的数字，则应该没问题。

Answer 3

如果可以引用原始数组"记录"和内部数组(即没有深度复制)，则可以使用以下内容：

function distinct(arr){
const res =[], //array with results
cmpArr = (a1,a2) => a1.length===a2.length && a1.every((i,ind) => a2[ind] === i),
cmpRec = (a1,a2) => [1,2,3].every(i=> cmpArr(a1[i],a2[i])); //compare 'records' for indices 1,2 and 3    
for(let subarr of arr){  	
subarr[2].sort(); //NB, this alters the source array. If this is not allowed, a work around can be created
if(!res.some(r => cmpRec(r,subarr))) //check if 'res' doesn't have an entry , based on the cmpRec function
	res.push(subarr);      
}
return res;
}
//test:
let input = [
[ [],[22],[1,13,17],[12],[] ], 
[ [],[22],[17,13,1],[12],[] ], 
[ [],[12],[1,13,17],[22],[] ], 
[ [11],[12],[13],[14],[15] ], 
[ [15],[14],[13],[12],[11] ]
];
console.log(distinct(input).map(JSON.stringify));