几年前我写了一个回溯正则表达式引擎,并意识到在看到您的问题时可以使用相同的算法。我不确定它是否是可能的最有效解决方案,但这是一种选择。
[更新:请参见答案末尾的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[] ) {
ArrayList arrayList;
for (int i = 1; i < argc; ++i) {
char* arg = argv[i];
arrayList.push_back(parseArray(arg,i,arg));
}
validateArrayList(arrayList);
printArrayList(arrayList);
Solution solution = solve(arrayList);
printSolution(solution);
}
Solution solve(const ArrayList& arrayList) {
typedef std::vector<int> ArrayHaveList;
typedef std::vector<ArrayHaveList> SmallNList;
typedef std::map<int,SmallNList> KMap;
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());
smallNList[pair.second-1].push_back(ai);
}
}
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 );
}
std::printf("]");
}
std::printf("]\n");
}
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;
bool impossible = false;
for (int ni = 0; ni < smallNList.size(); ++ni) {
const ArrayHaveList& arrayHaveList = smallNList[ni];
if (arrayHaveList.size() == 0) {
impossible = true;
break;
}
}
if (impossible) {
std::printf("trivially impossible: k=%d.\n", k );
continue;
}
std::vector<bool> burnList;
std::vector<int> currentCandidateIndex;
burnList.assign(arrayList.size(), false );
currentCandidateIndex.assign(arrayList.size(), -1 );
int ni;
for (ni = 0; ni < smallNList.size(); ++ni) {
std::printf("-> k=%d n=%d\n", k, ni+1 );
const ArrayHaveList& arrayHaveList = smallNList[ni];
bool gotOne = false;
for (int ci = currentCandidateIndex[ni]+1; ci < arrayHaveList.size(); ++ci) {
int candidateArrayIndex = arrayHaveList[ci];
if (!burnList[candidateArrayIndex]) {
burnList[candidateArrayIndex] = true;
currentCandidateIndex[ni] = ci;
gotOne = true;
break;
}
}
int niSave = ni;
if (!gotOne) {
if (ni == 0) {
std::printf("[%d,%d] failed, can't backtrack\n", k, ni+1 );
break;
}
int nip = ni-1;
const ArrayHaveList& prevArrayHaveList = smallNList[nip];
int cip = currentCandidateIndex[nip];
int aip = prevArrayHaveList[cip];
burnList[aip] = false;
currentCandidateIndex[ni] = -1;
ni = nip-1;
}
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 );
std::printf("burn:[");
for (int bi = 0; bi < burnList.size(); ++bi) {
if (bi > 0) std::printf(",");
std::printf("%s", burnList[bi] ? "X" : "O" );
}
std::printf("]\n");
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 );
}
std::printf("]\n");
}
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 );
}
std::printf("]\n");
solution.push_back(k);
} else {
std::printf("*** FAILED ***: k=%d\n", k );
}
}
return solution;
}
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);
if (*arg == ',') {
++arg;
skipWhite(arg);
}
} 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);
}
}
return array;
}
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);
}
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);
}
arg = endptr;
return (int)landing;
}
void validateArrayList(const ArrayList& arrayList) {
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;
}
}
}
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 );
}
std::printf("]\n");
}
}
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 );
}
std::printf("]\n");
}
void skipWhite(char*& a) {
while (*a != '\0' && std::isspace(*a))
++a;
}
这是一个使用您的示例数据的演示:
ls;
g++ a.cpp -o a;
ls;
./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]]';
为了演示您可以使用此代码轻松测试来自 shell 的不同输入,这里有一些微不足道的案例:
./a;
./a '[]';
./a '[[1,1]]';
./a '[[1,1],[2,2]]' '[[2,1],[1,2],[3,2],[3,1]]';
解释
这个问题有点复杂,但我会尽力解释它的工作原理。
首先,我编写了很多“脚手架”代码,用于解析命令行参数中的数组数据。每个命令行参数都应包含一个由[]
分隔的单个数组,在外部括号内可以有零个或多个以[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/
n \in [1..N]
,但在你的答案中n=7
,而且N=3
。我只是没理解这个问题。 - Juan Lopes