检查几组对是否覆盖给定的一对对

Question

假设我们有N成对的数组,例如N=3:

A ₁ =[ [3,2], [4,1], [5,1], [7,1], [7,2], [7,3] ]

阿₂ =[ [3,1], [3,2], [4,1], [4,2], [4,3], [5,3], [7,2] ]

A ₃ =[ [4,1], [5,1], [5,2], [7,1] ]

我们可以假设每个数组中的对按第一个数字排序,然后按第二个数字排序.此外,同一对不会多次出现在同一个数组中(同一对可以出现在多个数组中,如上所示).

每对中的数字是任意整数> = 1.

我怎么能找到k满足的所有东西:

(简单来说,[k,1], [k,2], ... , [k,N]存在于不同的数组中)

上述示例的预期结果是:[5, 7].

注意:速度是算法最重要的因素,然后是内存.如果它有助于优化速度/内存,请假设N <= 10.数组中的对数可以是~50000.

Answer 1

计划

创建一个数据对象（称之为data, data={}），如下所示：

对象中的每个键都是k 个候选，即，它是所有对集合中每个唯一的第一个坐标值。在上面的例子中，键是[3, 4, 5, 7]。键的值是一个包含元素 1..N 的数组，表示 A ₁ ..A _n。每个数组中的元素都是该数组中出现的与第一个坐标值匹配的第二个坐标值。对于上面的例子，data[3][1]=[2]因为坐标 [3,1] ∈ A ₂ data[3][2]=[1,2]，因为 [3,2] ∈ A ₁和 A ₂。

从那里开始，遍历每个找到的 k 值。如果data[k]其中有少于 N 个数组，则丢弃它，因为它显然不起作用。

从那里开始，检测 P ₁ ...P _n是否成立，我的想法是：生成 中数组的所有排列data[k]，对于每个排列集 AP ₁ ...AP _n（AP=A 排列），看看 1 是否在AP ₁、2 位于 AP ₂中……依此类推。如果找到了每个 n，我们就找到了 ak！我必须实际编写代码才能确定它是否有效，因此，下面是实际代码。我借用了这个函数来生成排列。

    var permArr, usedChars, found;
    //found ks go here
    found = [];

    //needed later
    function permute(input, start) {
        if (start === true) {
            permArr = [];
            usedChars = [];
        }
        var i, ch;
        for (i = 0; i < input.length; i++) {
            ch = input.splice(i, 1)[0];
            usedChars.push(ch);
            if (input.length === 0) {
                permArr.push(usedChars.slice());
            }
            permute(input);
            input.splice(i, 0, ch);
            usedChars.pop();
        }
        return permArr;
    }

    //the main event
    function findK(arrays) {

        //ok, first make an object that looks like this:
        //each key in the object is a k candidate, that is, its every unique first coordinate 
        //value in a pair. the value in array with elements 1..N, which represents A_1..A_n.
        //The elements in that array are each 2nd coordinate value that appears in that array 
        //matched with the first coordinate value, ie, data[3][1] has the array [2] 
        //because coordinate [3,1] is found in A_2.

        data = {};
        var N = arrays.length;
        for (var k = 0; k < N; k++) {
            //0/1 indexing
            var n = k + 1;
            for (var i = 0; i < arrays[k].length; i++) {
                var c1 = arrays[k][i][0];
                var c2 = arrays[k][i][1];
                if (!(c1 in data)) {
                    data[c1] = [];
                }
                if (!(c2 in data[c1])) {
                    data[c1][c2] = [];
                }
                data[c1][c2].push(n);
            }
        }
        data2 = [];


        //next, look at what we have. If any data[k] has less than n elements, disregard it
        //because not all of 1..N is represented. if it does, we need to test that it works,
        //that is, for each n in 1..N, you can find each value in a different array.
        //how do we do that? idea: go through every permutation of the N arrays, then 
        //count up from 1 to n and see if each n is in subarray_n

        //get all permutations
        //make an array from 1 to n
        var arr = [];
        for (var n = 1; n <= N; n++) {
            arr.push(n);
        }
        perms = permute(arr, true);

        for (k in data) {

            if (Object.keys(data[k]).length < N) {
                //not all 3 arrays are represented
                continue;
            }
            else {

                //permute them
                for (i in perms) {
                    if (found.indexOf(k) > -1) {
                        continue;
                    }
                    //permuations
                    //permutated array
                    var permuted = [undefined];
                    for (var j in perms[i]) {
                        permuted.push(data[k][perms[i][j]]);
                    }
                    //we have the permuted array, check for the existence of 1..N
                    var timesFound = 0;
                    console.log(permuted);
                    for (var n = 1; n <= N; n++) {
                        if (permuted[n].indexOf(n) > -1) {
                            timesFound++;
                        }
                    }
                    //if timesFound=N, it worked!
                    if (timesFound === N) {
                        found.push(k);
                    }

                }

                if (found.indexOf(k) > -1) {
                    continue;
                }
            }

        }

        //found is stringy, make it have ints
        for (i = 0; i < found.length; i++) {
            found[i] = parseInt(found[i]);
        }
        return found;
    }

结果

findK( [
            [[3, 2], [4, 1], [5, 1], [7, 1], [7, 2], [7, 3]]
                    , [[3, 1], [3, 2], [4, 1], [4, 2], [4, 3], [5, 3], [7, 2]]
                    , [[4, 1], [5, 1], [5, 2], [7, 1]]
        ] ); //[5,7]