Given ['RENE','ADRIANA','ANDRES'], I should find all possible pairs.

The test gives me the correct output as ['ADRIANA-RENE', 'ADRIANA-ANDRES', 'RENE-ANDRES'].

I already wrote a code using backtrack recursion, but most of the examples I've seen start from the beginning of the array (as obvious), and so does my solution. ['RENE-ADRIANA','RENE-ANDRES','ADRIANA-ANDRES']

I know they are the same, however, I am afraid my solution would not pass automated tests because it is not exact.

I believe they are using some sort of "binary search" starting from the middle and then continuing left before going right, although, I've been unable to write this code myself. I am not aware if there is an algorithm to find the possible combinations from a given array starting from the middle.

CodePudding user response：

Clearly, you can enumerate pairs using any order you choose. Just reorder the vector (or create a vector of indices into the original vector) in the desired order, and then run the standard enumeration algorithm.

But I doubt that is what was done in this case.

For an arbitrary vector of values, one thing you would probably want to do is eliminate duplicates. You could do that by first placing the values into a "set" datatype (or whatever equivalent is implemented by the target language), and then create the pairs by successively removing an element from the set:

# Pseudo-code
# Generate all pairs from the vector of elements V
Let S by an empty set
For each element v in V: add v to S
While S is not empty:
    Remove an element of S. Let v be the removed element.
    For each (remaining) element w in S, emit the pair <v, w>

The order of pairs generated by the above algorithm will clearly depend on the order in which the Set implementation removes elements, which is typically an implementation detail. Some implementations might always remove the lexicographically first element; others might remove the least-recently added element; others might remove the element whose hash value is the smallest. Etc.

Note that the above algorithm does not emit pairs <v, v>, even if v appears twice in the original vector. A minor modification would allow for that case (which requires keeping an auxiliary dataset of duplicated elements).

If the order of pairs is not defined in the requirements document, then a tester would have to allow any ordering. A possibly more interesting question than generating pairs would be to write such a tester. One possibility would be to compute the number of expected pairs. Then each pair in the proposed solution would be validated by checking that both elements are in the supplied vector, and then normalised by putting the two elements in some canonical order. Finally, the normalised list of pairs would be checked for duplicates (by sorting it or by putting it into a Set), and then the count would be checked against the expected pair count. You might enjoy fleshing out that description.

CodePudding user response：

It looks like the main trick here is iterating over all pairs of indices your array, in some sort of alternating way. I've reformulated your problem to something more generic/simpler to outline. Basically, given a length N array, generate all pairs of indices where the first index should start from the middle and the next indices should alternate from the left, then right to it. I'll assume that the next first index should be chosen in an alternating way, from left to right.

Here are a few cases

N = 3 (your example)
[
  (1, 0)
  (1, 2)
  (0, 2)
]

N = 4
[
  (2, 1)
  (2, 3)
  (2, 0)
  (1, 0)
  (1, 3)
  (3, 0)
]

N = 5
[
  (2, 1)
  (2, 3)
  (2, 0)
  (1, 0)
  (1, 3)
  (1, 4)
  (3, 0)
  (3, 4)
  (0, 4)
]

We can model this iteration iteratively via breadth first search:

1. Initialize a queue Q, a middle value mid equal to N/2. Let left, right be equal to mid-1 and mid 1 respectively.

2. Insert mid into Q

3. Pop Q and assign it to mid

4. Generate alternating pairs starting from mid, using left and right as the immediate left/right starting points

5. If you're on an odd cycle of 3., insert left into Q and decrement it by 1. Otherwise insert right into Q and increment it by 1. Don't perform insertion if the value to be inserted is out of bounds.

6. Loop back to 3, until Q is empty.

This should give the desired traversal and does indeed cover all pairs of indices exactly once (my implementation worked until N = 1000; after that it started taking quite a bit of time).

To apply this to your problem, just take each index pair and combine the strings at those indices.