A few years ago, I wrote a backtracking regex mechanism, and I realized when I looked at your problem that the same algorithm could be used here. I'm not sure if this is the most effective solution, but this is one option.
[Update: see the end of the answer for the JavaScript port.] I wrote C ++ code because it is my favorite language, and from the original version of your question it was not clear what language it was (I started writing code before your second revision, it seemed to me from version 1 that your question was agnostic), but I'm sure it should be possible to port this from C ++ to JavaScript; std::vector will become Array / [] , and std::map will become the plain old Object / {} for starters.
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 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=%dn=%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()
Here is an example with your example data:
ls;
And just to demonstrate the ease with which you can use this code to test different shell inputs, here are a few trivial cases:
./a;
Description
This is pretty complicated, but I will do my best to explain how it works.
First of all, there is a lot of "scaffolding" code that I wrote to parse the array data from command line arguments. It is expected that each command line argument will contain one array, limited to [] , with zero or more pairs in the format [k,n] inside the outer brackets. Couples themselves can be separated by commas, but I made this optional. Spaces are allowed almost everywhere, except, of course, not within individual numbers.
I do a very strict check, both during parsing and after parsing. Validation after analysis consists in the fact that all n values (that is the second number in each pair) have only 1..N values (where n , of course, is automatically determined from the number of arrays provided) and that there are no duplicate pairs in each individual array, which was the requirement indicated in your question, and that requirement depends on my algorithm.
Thus, a high-level process is (1) parsing plus basic parsing, (2) validation after parsing, (3) solution, and (4) printing of the solution. I also included verbose debug output at different times, as you can see from the demos.
As for the real solution algorithm, the first thing to recognize is that all k are independent of each other; the first number of each pair effectively isolates its significance only from k . Thus, I developed data structures and an algorithm for working separately with each possible value of k , which could be a solution to the problem.
The second recognition is that for a given k , since you need [k,n] exist in some kind of array for all values of n in 1..N , and you prohibit the assignment of the same array to different n , and there are exactly n arrays, what you really do is the "distribution" or "distribution" of arrays among all the values of n .
The third thing to be recognized is that for each pair [k,n] this pair can be included in several arrays, and therefore there can be several “candidates” for which the array is assigned to the given n . This means that we need to check the various distributions of arrays for possible n values to find if there is a way to allocate all arrays for all n values.
The algorithm works by first scanning all pairs in all arrays and creating a “list of candidates” for arrays that contain the given [k,n] . These candidate lists ( ArrayHaveList ) are divided into a card with key k ( KMap ) and then divided into a vector with index n-1 ( SmallNList ). Thus, for each value of k represented in the input, there will be n "candidate vectors", each of which is zero or more (well, at least one of the vectors must be one or more in length, since at least one pair must exist for k if it is being processed at all).
Then, for each k value, I initialize two important vectors: (1) the "burn" vector ( burnList ), which is used to prevent the same array from being allocated for several n values, and (2) the candidate selection vector ( currentCandidateIndex ), which is used to track which candidate from the set of candidates for each value of n is currently “verified”. Each of them will have a length equal to n . The candidate selection vector is the basis of the inverse tracking algorithm; he tracks “where we are” in the backtracking process.
Each n value is assigned to the array until we can assign the next n value to the array, because none of its possible arrays is available (that is, they are all “burned”). At this point, we need to undo previous assignments of n values in order to try to “free” the array for the failed n value, if possible. This requires a reverse cycle n , which is written so as to always advance the current candidate choice from what it was before the current iteration. This allows you to work both during the first iteration with a given value of n , and in subsequent iterations of repeated tracking.
The process ends when either we must step back from n=1 , which is impossible because there is no previous n value to return, in which case the k value does not pass the test, or we end the n cycle that is successfully assigned to all n values in the array.
At any time, we must take care to keep the record list correct (this means assigning true when a particular array is assigned to n , and resetting the previous assignment to n to false when the next n value is not executed and must be returned) is correct (this means that it registers the index of the candidate in the array, which is assigned when it is assigned, and its reset (for n in the current iteration) to -1 when we are preparing to return the previous n , which is necessary for us to "start with zero "in flow n when we return to it after returning back to the previous n ).
I also included a trivial check to see if n values are zero candidates for a given k , and in this case it would be wasteful to run the entire backtracking algorithm for that k , since the code fails repeatedly with a zero candidate n and returns all over all candidates of all previous values of n .
Javascript
Well, that was a little annoying. I have ported the code from C ++ to JavaScript and it seems to work:
... bang! Stack overflow will not allow me to send a response of more than 30,000 characters, so I cannot include my JavaScript source code as a piece of code. We will have to depend on JSFiddle. See here:
http://jsfiddle.net/kobyde5z/