检查多组配对是否覆盖了给定的一组配对

Question

假设我们有N个成对的数组，例如当N=3时：

A1 = [ [3,2], [4,1], [5,1], [7,1], [7,2], [7,3] ]

A2 = [ [3,1], [3,2], [4,1], [4,2], [4,3], [5,3], [7,2] ]

A3 = [ [4,1], [5,1], [5,2], [7,1] ]

可以假定每个数组中的成对都按第一个数字和第二个数字排序。同样的成对在同一数组中不会出现超过一次（如上所示，同样的成对可能出现在多个数组中）。

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

如何找到所有满足以下条件的k：

[k,1]，[k,2]，......，[k,N] 在不同的数组中存在

上述例子的预期结果是：[5,7]。

注意：速度是算法的最重要因素，然后是内存。如果为了优化速度/内存而有所帮助，则假定N <= 10。 数组中对的数量可以约为50000。

- Misha Moroshko

---

我不明白。你说 n \in [1..N]，但在你的答案中 n=7，而且 N=3。我只是没理解这个问题。 - Juan Lopes

n不等于7，2个k值分别为5和7。 - chiliNUT

@chiliNUT 噢，对不起，我现在看到了，谢谢 :) - Juan Lopes

如果我没有误解问题，4也可以是[5,7]的答案。我是否错过了问题的某些内容或是您打错了？ - meth

@MishaMoroshko 哈哈，现在我明白了。感谢您的澄清。 - meth

Answer 1

几年前我写了一个回溯正则表达式引擎，并意识到在看到您的问题时可以使用相同的算法。我不确定它是否是可能的最有效解决方案，但这是一种选择。

[更新：请参见答案末尾的JavaScript端口。] 我用C++编写代码，因为这是我最喜欢的语言，而且从您问题的最初修订版中并不清楚这是针对哪种语言（在您发布第二个版本之前我就开始写代码了；从第一个版本来看，您的问题似乎与语言无关），但我确信应该可以将其从C++移植到JavaScript; std::vector将变为Array/[] 和std::map将变成普通的Object/{}，等等。

C++

#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <climits>
#include <cerrno>
#include <cctype>

#include <vector>
#include <map>

typedef std::pair<int,int> Pair;
typedef std::vector<Pair> Array;
typedef std::vector<Array> ArrayList;

typedef std::vector<int> Solution;

Solution solve(const ArrayList& arrayList);
Array parseArray(char*& arg, int i, char* argFull );
Pair parsePair(char*& arg, int i, char* argFull );
int parseNumber(char*& arg, int i, char* argFull );
void validateArrayList(const ArrayList& arrayList);
void printArrayList(const ArrayList& arrayList);
void printSolution(const Solution& solution);
void skipWhite(char*& a);

int main(int argc, char *argv[] ) {

    // parse out arrays
    ArrayList arrayList;
    for (int i = 1; i < argc; ++i) {
        char* arg = argv[i];
        arrayList.push_back(parseArray(arg,i,arg));
    } // end for
    validateArrayList(arrayList);
    printArrayList(arrayList);

    // solve
    Solution solution = solve(arrayList);
    printSolution(solution);

} // end main()

Solution solve(const ArrayList& arrayList) {

    typedef std::vector<int> ArrayHaveList; // use the 0-based index for ease
    typedef std::vector<ArrayHaveList> SmallNList;
    typedef std::map<int,SmallNList> KMap;

    // 1: collect all possible k's into a map
    // during this collection, will precompute which arrays have which "small n" values for each k
    KMap kmap;
    for (int ai = 0; ai < arrayList.size(); ++ai) {
        const Array& array = arrayList[ai];
        for (int pi = 0; pi < array.size(); ++pi) {
            const Pair& pair = array[pi];
            std::pair<KMap::iterator,bool> insertRet = kmap.insert(std::pair<int,SmallNList>(pair.first,SmallNList()));
            SmallNList& smallNList = insertRet.first->second;
            if (insertRet.second) smallNList.resize(arrayList.size());
            assert(pair.second >= 1 && pair.second <= arrayList.size()); // should already have been validated
            smallNList[pair.second-1].push_back(ai); // don't have to check because same pair cannot appear in same array more than once (already validated this)
        } // end for
    } // end for
    // debug kmap
    std::printf("----- KMap -----\n");
    for (KMap::iterator it = kmap.begin(); it != kmap.end(); ++it) {
        int k = it->first;
        const SmallNList& smallNList = it->second;
        std::printf("%d: [", k );
        for (int ni = 0; ni < smallNList.size(); ++ni) {
            const ArrayHaveList& arrayHaveList = smallNList[ni];
            if (ni > 0) std::printf(",");
            std::printf("%d:[", ni+1 );
            for (int ci = 0; ci < arrayHaveList.size(); ++ci) {
                int ai = arrayHaveList[ci];
                if (ci > 0) std::printf(",");
                std::printf("%d", ai+1 );
            } // end for
            std::printf("]");
        } // end for
        std::printf("]\n");
    } // end for

    // 2: for each k, and then for each small n, go through each possible "candidate" array that has that small n value for that k, and see if we can satisfy all small n values for that k
    std::printf("----- solving algorithm -----\n");
    Solution solution;
    for (KMap::iterator it = kmap.begin(); it != kmap.end(); ++it) {

        int k = it->first;
        const SmallNList& smallNList = it->second;

        // actually, first do a trivial check to see if any small n values have no candidates at all; then this is impossible, and we can reject this k
        bool impossible = false; // assumption
        for (int ni = 0; ni < smallNList.size(); ++ni) { // ni is "small n index", meaning 0-based
            const ArrayHaveList& arrayHaveList = smallNList[ni];
            if (arrayHaveList.size() == 0) {
                impossible = true;
                break;
            } // end if
        } // end for
        if (impossible) {
            std::printf("trivially impossible: k=%d.\n", k );
            continue;
        } // end if

        // now run the main backtracking candidate selection algorithm
        std::vector<bool> burnList; // allows quickly checking if a candidate array is available for a particular [k,n] pair (indexed by ai)
        std::vector<int> currentCandidateIndex; // required for backtracking candidate selections; keeps track of the current selection from the list of candidates for each [k,n] pair (indexed by ni)
        burnList.assign(arrayList.size(), false );
        currentCandidateIndex.assign(arrayList.size(), -1 ); // initialize to -1, so on first iteration of any given ni it will automatically be incremented to the first index, zero
        int ni; // declared outside for-loop for accessibility afterward
        for (ni = 0; ni < smallNList.size(); ++ni) { // ni is "small n index", meaning 0-based representation of small n

            // very important: this loop is the base for the backtracking algorithm, thus, it will be continued (with modified ni) when we need to backtrack, thus, it needs to be general for these cases

            std::printf("-> k=%d n=%d\n", k, ni+1 );

            const ArrayHaveList& arrayHaveList = smallNList[ni];

            // attempt to find a candidate array that is unburnt
            bool gotOne = false; // assumption
            for (int ci = currentCandidateIndex[ni]+1; ci < arrayHaveList.size(); ++ci) { // start ci at previous best candidate index plus one
                int candidateArrayIndex = arrayHaveList[ci];
                if (!burnList[candidateArrayIndex]) { // available
                    // now we can take this array for this [k,n] pair
                    burnList[candidateArrayIndex] = true;
                    currentCandidateIndex[ni] = ci;
                    gotOne = true;
                    break;
                } // end if
            } // end for

            // react to success or failure of finding an available array for this [k,n] pair
            int niSave = ni; // just for debugging
            if (!gotOne) {
                // we were unable to find a candidate for this [k,n] pair that inhabits a currently-available array; thus, must backtrack previous small n values
                if (ni == 0) { // uh-oh; we can't backtrack at all, thus this k is not a solution; break out of ni loop
                    std::printf("[%d,%d] failed, can't backtrack\n", k, ni+1 );
                    break;
                } // end if
                // now we have ni > 0, so we can backtrack to previous ni's
                int nip = ni-1;
                const ArrayHaveList& prevArrayHaveList = smallNList[nip];
                int cip = currentCandidateIndex[nip]; // get currently-used candidate index for this previous small n
                int aip = prevArrayHaveList[cip]; // get actual currently-used array index for this previous small n
                // unconditionally unburn it
                burnList[aip] = false;
                // reset outselves (current candidate index for current iteration ni) back to -1, so when we "return" to this ni from the backtrack, it'll be ready to check again
                // note: we don't have to reset the burn list element, because it can't have been set to true for the current iteration ni; that only happens when we find an available array
                currentCandidateIndex[ni] = -1;
                // reset the iteration var ni to nip-1, so that it will be incremented back into nip
                ni = nip-1;
            } // end if

            // debug burn list, current candidate index, and decision made by the above loop (not in that order)
            // decision
            if (gotOne)
                std::printf("[%d,%d] got in array %d\n", k, niSave+1, arrayHaveList[currentCandidateIndex[niSave]]+1 );
            else
                std::printf("[%d,%d] failed\n", k, niSave+1 );
            // burn list
            std::printf("burn:[");
            for (int bi = 0; bi < burnList.size(); ++bi) {
                if (bi > 0) std::printf(",");
                std::printf("%s", burnList[bi] ? "X" : "O" );
            } // end for
            std::printf("]\n");
            // current candidate index
            std::printf("candidate:[");
            for (int ni2 = 0; ni2 < currentCandidateIndex.size(); ++ni2) {
                if (ni2 > 0) std::printf(",");
                int ci = currentCandidateIndex[ni2];
                if (ci == -1)
                    std::printf("-");
                else
                    std::printf("%d", ci+1 );
            } // end for
            std::printf("]\n");

        } // end for
        // test if we reached the end of all ni's
        if (ni == smallNList.size()) {
            std::printf("*** SUCCESS ***: k=%d has array order [", k );
            for (int ni = 0; ni < currentCandidateIndex.size(); ++ni) {
                const ArrayHaveList& arrayHaveList = smallNList[ni];
                int ci = currentCandidateIndex[ni];
                int ai = arrayHaveList[ci];
                if (ni > 0) std::printf(",");
                std::printf("%d", ai+1 );
            } // end for
            std::printf("]\n");
            solution.push_back(k);
        } else {
            std::printf("*** FAILED ***: k=%d\n", k );
        } // end if

    } // end for

    return solution;

} // end solve()

Array parseArray(char*& arg, int i, char* argFull ) {
    skipWhite(arg);
    if (*arg != '[') { std::fprintf(stderr, "invalid syntax from \"%s\": no leading '[': argument %d \"%s\".\n", arg, i, argFull ); std::exit(1); }
    ++arg;
    skipWhite(arg);
    Array array;
    while (true) {
        if (*arg == ']') {
            ++arg;
            skipWhite(arg);
            if (*arg != '\0') { std::fprintf(stderr, "invalid syntax from \"%s\": trailing characters: argument %d \"%s\".\n", arg, i, argFull ); std::exit(1); }
            break;
        } else if (*arg == '[') {
            array.push_back(parsePair(arg,i,argFull));
            skipWhite(arg);
            // allow single optional comma after any pair
            if (*arg == ',') {
                ++arg;
                skipWhite(arg);
            } // end if
        } else if (*arg == '\0') {
            std::fprintf(stderr, "invalid syntax from \"%s\": unexpected end-of-array: argument %d \"%s\".\n", arg, i, argFull ); std::exit(1);
        } else {
            std::fprintf(stderr, "invalid syntax from \"%s\": invalid character '%c': argument %d \"%s\".\n", arg, *arg, i, argFull ); std::exit(1);
        } // end if
    } // end for
    return array;
} // end parseArray()

Pair parsePair(char*& arg, int i, char* argFull ) {
    assert(*arg == '[');
    ++arg;
    skipWhite(arg);
    int first = parseNumber(arg,i,argFull);
    skipWhite(arg);
    if (*arg != ',') { std::fprintf(stderr, "invalid syntax from \"%s\": non-',' after number: argument %d \"%s\".\n", arg, i, argFull ); std::exit (1); }
    ++arg;
    skipWhite(arg);
    int second = parseNumber(arg,i,argFull);
    skipWhite(arg);
    if (*arg != ']') { std::fprintf(stderr, "invalid syntax from \"%s\": non-']' after number: argument %d \"%s\".\n", arg, i, argFull ); std::exit (1); }
    ++arg;
    return Pair(first,second);
} // end parsePair()

int parseNumber(char*& arg, int i, char* argFull ) {
    char* endptr;
    unsigned long landing = strtoul(arg, &endptr, 10 );
    if (landing == 0 && errno == EINVAL || landing == ULONG_MAX && errno == ERANGE || landing > INT_MAX) {
        std::fprintf(stderr, "invalid syntax from \"%s\": invalid number: argument %d \"%s\".\n", arg, i, argFull );
        std::exit(1);
    } // end if
    arg = endptr;
    return (int)landing;
} // end parseNumber()

void validateArrayList(const ArrayList& arrayList) {
    // note: all numbers have already been forced to be natural numbers during parsing
    // 1: validate that all seconds are within 1..N
    // 2: validate that we don't have duplicate pairs in the same array
    typedef std::vector<bool> SecondSeenList;
    typedef std::map<int,SecondSeenList> FirstMap;
    for (int ai = 0; ai < arrayList.size(); ++ai) {
        const Array& array = arrayList[ai];
        FirstMap firstMap;
        for (int pi = 0; pi < array.size(); ++pi) {
            const Pair& pair = array[pi];
            if (pair.second == 0) { std::fprintf(stderr, "invalid second number %d: less than 1.\n", pair.second ); std::exit(1); }
            if (pair.second > arrayList.size()) { std::fprintf(stderr, "invalid second number %d: greater than N=%d.\n", pair.second, arrayList.size() ); std::exit(1); }
            std::pair<FirstMap::iterator,bool> insertRet = firstMap.insert(std::pair<int,SecondSeenList>(pair.first,SecondSeenList()));
            SecondSeenList& secondSeenList = insertRet.first->second;
            if (insertRet.second) secondSeenList.assign(arrayList.size(), false );
            if (secondSeenList[pair.second-1]) { std::fprintf(stderr, "invalid array %d: duplicate pair [%d,%d].\n", ai+1, pair.first, pair.second ); std::exit(1); }
            secondSeenList[pair.second-1] = true;
        } // end for
    } // end for
} // end validateArrayList()

void printArrayList(const ArrayList& arrayList) {
    std::printf("----- parsed arrays -----\n");
    for (int ai = 0; ai < arrayList.size(); ++ai) {
        const Array& array = arrayList[ai];
        std::printf("A[%d] == [", ai+1 );
        for (int pi = 0; pi < array.size(); ++pi) {
            const Pair& pair = array[pi];
            if (pi > 0) std::printf(",");
            std::printf("[%d,%d]", pair.first, pair.second );
        } // end for
        std::printf("]\n");
    } // end for
} // end printArrayList()

void printSolution(const Solution& solution) {
    std::printf("----- solution -----\n");
    std::printf("[");
    for (int si = 0; si < solution.size(); ++si) {
        int k = solution[si];
        if (si > 0) std::printf(",");
        std::printf("%d", k );
    } // end for
    std::printf("]\n");
} // end printSolution()

void skipWhite(char*& a) {
    while (*a != '\0' && std::isspace(*a))
        ++a;
} // end skipWhite()

这是一个使用您的示例数据的演示：

ls;
## a.cpp

g++ a.cpp -o a;

ls;
## a.cpp  a.exe*

./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] ]' '[ [4,1], [5,1], [5,2], [7,1]]';
## ----- parsed arrays -----
## A[1] == [[3,2],[4,1],[5,1],[7,1],[7,2],[7,3]]
## A[2] == [[3,1],[3,2],[4,1],[4,2],[4,3],[5,3],[7,2]]
## A[3] == [[4,1],[5,1],[5,2],[7,1]]
## ----- KMap -----
## 3: [1:[2],2:[1,2],3:[]]
## 4: [1:[1,2,3],2:[2],3:[2]]
## 5: [1:[1,3],2:[3],3:[2]]
## 7: [1:[1,3],2:[1,2],3:[1]]
## ----- solving algorithm -----
## trivially impossible: k=3.
## -> k=4 n=1
## [4,1] got in array 1
## burn:[X,O,O]
## candidate:[1,-,-]
## -> k=4 n=2
## [4,2] got in array 2
## burn:[X,X,O]
## candidate:[1,1,-]
## -> k=4 n=3
## [4,3] failed
## burn:[X,O,O]
## candidate:[1,1,-]
## -> k=4 n=2
## [4,2] failed
## burn:[O,O,O]
## candidate:[1,-,-]
## -> k=4 n=1
## [4,1] got in array 2
## burn:[O,X,O]
## candidate:[2,-,-]
## -> k=4 n=2
## [4,2] failed
## burn:[O,O,O]
## candidate:[2,-,-]
## -> k=4 n=1
## [4,1] got in array 3
## burn:[O,O,X]
## candidate:[3,-,-]
## -> k=4 n=2
## [4,2] got in array 2
## burn:[O,X,X]
## candidate:[3,1,-]
## -> k=4 n=3
## [4,3] failed
## burn:[O,O,X]
## candidate:[3,1,-]
## -> k=4 n=2
## [4,2] failed
## burn:[O,O,O]
## candidate:[3,-,-]
## -> k=4 n=1
## [4,1] failed, can't backtrack
## *** FAILED ***: k=4
## -> k=5 n=1
## [5,1] got in array 1
## burn:[X,O,O]
## candidate:[1,-,-]
## -> k=5 n=2
## [5,2] got in array 3
## burn:[X,O,X]
## candidate:[1,1,-]
## -> k=5 n=3
## [5,3] got in array 2
## burn:[X,X,X]
## candidate:[1,1,1]
## *** SUCCESS ***: k=5 has array order [1,3,2]
## -> k=7 n=1
## [7,1] got in array 1
## burn:[X,O,O]
## candidate:[1,-,-]
## -> k=7 n=2
## [7,2] got in array 2
## burn:[X,X,O]
## candidate:[1,2,-]
## -> k=7 n=3
## [7,3] failed
## burn:[X,O,O]
## candidate:[1,2,-]
## -> k=7 n=2
## [7,2] failed
## burn:[O,O,O]
## candidate:[1,-,-]
## -> k=7 n=1
## [7,1] got in array 3
## burn:[O,O,X]
## candidate:[2,-,-]
## -> k=7 n=2
## [7,2] got in array 1
## burn:[X,O,X]
## candidate:[2,1,-]
## -> k=7 n=3
## [7,3] failed
## burn:[O,O,X]
## candidate:[2,1,-]
## -> k=7 n=2
## [7,2] got in array 2
## burn:[O,X,X]
## candidate:[2,2,-]
## -> k=7 n=3
## [7,3] got in array 1
## burn:[X,X,X]
## candidate:[2,2,1]
## *** SUCCESS ***: k=7 has array order [3,2,1]
## ----- solution -----
## [5,7]

为了演示您可以使用此代码轻松测试来自 shell 的不同输入，这里有一些微不足道的案例：

./a;
## ----- parsed arrays -----
## ----- KMap -----
## ----- solving algorithm -----
## ----- solution -----
## []

./a '[]';
## ----- parsed arrays -----
## A[1] == []
## ----- KMap -----
## ----- solving algorithm -----
## ----- solution -----
## []

./a '[[1,1]]';
## ----- parsed arrays -----
## A[1] == [[1,1]]
## ----- KMap -----
## 1: [1:[1]]
## ----- solving algorithm -----
## -> k=1 n=1
## [1,1] got in array 1
## burn:[X]
## candidate:[1]
## *** SUCCESS ***: k=1 has array order [1]
## ----- solution -----
## [1]

./a '[[1,1],[2,2]]' '[[2,1],[1,2],[3,2],[3,1]]';
## ----- parsed arrays -----
## A[1] == [[1,1],[2,2]]
## A[2] == [[2,1],[1,2],[3,2],[3,1]]
## ----- KMap -----
## 1: [1:[1],2:[2]]
## 2: [1:[2],2:[1]]
## 3: [1:[2],2:[2]]
## ----- solving algorithm -----
## -> k=1 n=1
## [1,1] got in array 1
## burn:[X,O]
## candidate:[1,-]
## -> k=1 n=2
## [1,2] got in array 2
## burn:[X,X]
## candidate:[1,1]
## *** SUCCESS ***: k=1 has array order [1,2]
## -> k=2 n=1
## [2,1] got in array 2
## burn:[O,X]
## candidate:[1,-]
## -> k=2 n=2
## [2,2] got in array 1
## burn:[X,X]
## candidate:[1,1]
## *** SUCCESS ***: k=2 has array order [2,1]
## -> k=3 n=1
## [3,1] got in array 2
## burn:[O,X]
## candidate:[1,-]
## -> k=3 n=2
## [3,2] failed
## burn:[O,O]
## candidate:[1,-]
## -> k=3 n=1
## [3,1] failed, can't backtrack
## *** FAILED ***: k=3
## ----- solution -----
## [1,2]

解释

这个问题有点复杂，但我会尽力解释它的工作原理。

首先，我编写了很多“脚手架”代码，用于解析命令行参数中的数组数据。每个命令行参数都应包含一个由[]分隔的单个数组，在外部括号内可以有零个或多个以[k，n]格式的对。这些对本身可以用逗号分隔，但我将其设置为可选项。除了不允许在单个数字内部之外，几乎可以在任何地方使用空格。

我进行非常严格的验证，既在解析期间，也在解析后。解析后的验证包括强制所有n值（即每个对中的第二个数字）只在1..N范围内（其中N当然是根据提供的数组数量自动确定的），并强制要求在任何单个数组中没有重复的对，这是您在问题中指定的要求，并且是我的算法所依赖的要求。

因此，高级过程是（1）解析加基本语法验证，（2）解析后验证，（3）求解和（4）打印解决方案。正如您从演示中看到的那样，我还在各个时段包含了详细的调试输出。

关于实际的解决算法，首先要认识到的是所有的 k 值彼此独立；每对数字的第一个数字有效地将其相关性隔离到只有该 k 值。因此，我设计了数据结构和算法，以便分别处理可能代表问题解决方案的每个可能的 k 值。

第二件要认识到的事情是，对于给定的 k 值，由于你需要 [k,n] 存在于 1..N 中所有 n 值的某个数组中，而且不允许将相同的数组分配给不同的 n 值，并且恰好有 N 个数组，所以你真正做的是“分配”或“分发”这些数组到所有 n 值中。

第三件需要认识的事情是，对于每个 [k,n] 对，该对可以被包含在多个数组中，因此可能会有多个“候选项”指定给定的 n 应该分配到哪个数组。这意味着我们需要检查将数组分配给可能的 n 值的不同分配方式，以找到是否有一种方法可以将所有数组分配给所有 n 值。

算法首先扫描所有数组中的所有对，并构造包含给定 [k,n] 的数组的“候选列表”。这些候选列表（ArrayHaveList）被分成一个以 k 为键的映射（KMap），并进一步分成一个索引为 n-1 的向量（SmallNList）。因此，对于输入数据中表示的每个 k 值，都将有 N 个“候选向量”，每个向量的长度为零或更多（至少其中一个向量必须具有长度为一或更多，因为如果完全不考虑 k 值，则必须存在至少一个对）。

然后，对于每个k值，我依次初始化两个重要的向量：（1）一个“烧毁”向量（burnList），用于防止将同一数组分配给多个n值；（2）一个“候选选择”向量（currentCandidateIndex），用于跟踪每个n值的候选数组集合中当前正在“尝试”的数组候选项。每个向量的长度都等于N。候选选择向量是回溯算法的关键所在；它跟踪回溯过程中的“位置”。

每个n值都被分配到一个数组中，直到我们无法将下一个n值分配给任何一个数组，因为它的候选数组都不可用（即它们都已经“烧毁”）。此时，我们需要回溯之前的n值分配，尝试“释放”一个数组以供失败的n值使用，如果可能的话。这需要反转n循环，它被编写为始终从当前迭代之前的任何候选选择中推进当前候选选择。这使得它在给定n值的第一次迭代和后续回溯迭代期间都能正常工作。

当我们必须从n = 1回溯时，该过程结束，因为没有先前的n值可回溯，此时k值未通过测试；或者我们完成了n循环，成功地将所有n值分配到一个数组中，此时过程也结束。

在任何时候，我们必须注意保持燃烧列表的正确性（这意味着当将特定数组分配给n值时，分配true，并在以下n值失败并必须回溯时将先前的n值分配重置为false），以及候选选择向量的正确性（这意味着在分配时捕获分配的数组候选索引，并在准备回溯前一个n时将其（对于当前迭代中的n）重置为-1，这是必要的，以便我们可以在回到它之后从头开始处理当前的n）。

我还包括了一个微不足道的检查，以查看任何给定k的n值是否具有零个候选项，如果是，则在该k上运行整个回溯算法将是浪费的，因为代码会反复在零候选项n上失败，并通过所有先前n值的所有候选项的重复多重性进行回溯。

JavaScript

好的，那有点烦人。我将代码从C++移植到JavaScript，似乎正在工作：

“Bah！Stack Overflow不让我提交超过30,000个字符的答案，所以我无法将我的JavaScript源代码作为代码片段包含在内。我们必须依靠JSFiddle。请看这里：”

http://jsfiddle.net/kobyde5z/

- bgoldst

Answer 2

计划

创建一个数据对象（称之为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=一个排列），看看1是否在AP₁中，2是否在AP₂中，依此类推。如果找到每个n，我们就找到了一个k！我不得不实际编写代码来确定它是否有效，所以下面是实际代码。我借用了this函数来生成排列。

    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]

- chiliNUT