Nearest permutation to given array

Question

Question

I have two arrays of integers A[] and B[]. Array B[] is fixed, I need to to find the permutation of A[] which is lexiographically smaller than B[] and the permutation is nearest to B[]. Here what I mean is:

for i in (0 <= i < n) abs(B[i]-A[i]) is minimum and A[] should be smaller than B[] lexiographically.

For Example:

A[]={1,3,5,6,7}

B[]={7,3,2,4,6}

So,possible nearest permutation of A[] to B[] is

A[]={7,3,1,6,5}

My Approach

Try all permutation of A[] and then compare that with B[]. But the time complexity would be (n! * n)

So is there any way to optimize this?

EDIT

n can be as large as 10^5

For better understanding

Answer 1

First, build an ordered map of the counts of the distinct elements of A.

Then, iterate forward through array indices (0 to n−1), "withdrawing" elements from this map. At each point, there are three possibilities:

• If i < n-1, and it's possible to choose A[i] == B[i], do so and continue iterating forward.
• Otherwise, if it's possible to choose A[i] < B[i], choose the greatest possible value for A[i] < B[i]. Then proceed by choosing the largest available values for all subsequent array indices. (At this point you no longer need to worry about maintaining A[i] <= B[i], because we're already after an index where A[i] < B[i].) Return the result.
• Otherwise, we need to backtrack to the last index where it was possible to choose A[i] < B[i], then use the approach in the previous bullet-point.
  • Note that, despite the need for backtracking, the very worst case here is three passes: one forward pass using the logic in the first bullet-point, one backward pass in backtracking to find the last index where A[i] < B[i] was possible, and then a final forward pass using the logic in the second bullet-point.

Because of the overhead of maintaining the ordered map, this requires O(n log m) time and O(m) extra space, where n is the total number of elements of A and m is the number of distinct elements. (Since m ≤ n, we can also express this as O(n log n) time and O(n) extra space.)

---

Note that if there's no solution, then the backtracking step will reach all the way to i == -1. You'll probably want to raise an exception if that happens.

---

Edited to add (2019-02-01):

In a now-deleted answer, גלעד ברקן summarizes the goal this way:

To be lexicographically smaller, the array must have an initial optional section from left to right where A[i] = B[i] that ends with an element A[j] < B[j]. To be closest to B, we want to maximise the length of that section, and then maximise the remaining part of the array.

So, with that summary in mind, another approach is to do two separate loops, where the first loop determines the length of the initial section, and the second loop actually populates A. This is equivalent to the above approach, but may make for cleaner code. So:

1. Build an ordered map of the counts of the distinct elements of A.
2. Initialize initial_section_length := -1.
3. Iterate through the array indices 0 to n−1, "withdrawing" elements from this map. For each index:
   • If it's possible to choose an as-yet-unused element of A that's less than the current element of B, set initial_section_length equal to the current array index. (Otherwise, don't.)
   • If it's not possible to choose an as-yet-unused element of A that's equal to the current element of B, break out of this loop. (Otherwise, continue looping.)
4. If initial_section_length == -1, then there's no solution; raise an exception.
5. Repeat step #1: re-build the ordered map.
6. Iterate through the array indices from 0 to initial_section_length-1, "withdrawing" elements from the map. For each index, choose an as-yet-unused element of A that's equal to the current element of B. (The existence of such an element is ensured by the first loop.)
7. For array index initial_section_length, choose the greatest as-yet-unused element of A that's less than the current element of B (and "withdraw" it from the map). (The existence of such an element is ensured by the first loop.)
8. Iterate through the array indices from initial_section_length+1 to n−1, continuing to "withdraw" elements from the map. For each index, choose the greatest element of A that hasn't been used yet.

This approach has the same time and space complexities as the backtracking-based approach.

Answer 2

There are n! permutations of A[n] (less if there are repeating elements).

Use binary search over range 0..n!-1 to determine k-th lexicographic permutation of A[] (arbitrary found example) which is closest lower one to B[].

Perhaps in C++ you can exploit std::lower_bound

Answer 3

Based on the discussion in the comment section to your question, you seek an array made up entirely of elements of the vector A that is -- in lexicographic ordering -- closest to the vector B.

For this scenario, the algorithm becomes quite straightforward. The idea is the same as as already mentioned in the answer of @ruakh (although his answer refers to an earlier and more complicated version of your question -- that is still displayed in the OP -- and is therefore more complicated):

• Sort A
• Loop over B and select the element of A that is closest to B[i]. Remove that element from the list.
• If no element in A is smaller-or-equal than B[i], pick the largest element.

Here is the basic implementation:

#include <string>
#include <vector>
#include <algorithm>

auto get_closest_array(std::vector<int> A, std::vector<int> const& B)
{
    std::sort(std::begin(A), std::end(A), std::greater<>{});

    auto select_closest_and_remove = [&](int i)
    {
        auto it = std::find_if(std::begin(A), std::end(A), [&](auto x) { return x<=i;});
        if(it==std::end(A))
        {
            it = std::max_element(std::begin(A), std::end(A));            
        }
        auto ret = *it;
        A.erase(it);
        return ret;
    };

    std::vector<int> ret(B.size());
    for(int i=0;i<(int)B.size();++i)
    {
        ret[i] = select_closest_and_remove(B[i]);
    }
    return ret;
}

Applied to the problem in the OP one gets:

int main()
{
    std::vector<int> A ={1,3,5,6,7};
    std::vector<int> B ={7,3,2,4,6};

    auto C = get_closest_array(A, B);

    for(auto i : C)
    {
        std::cout<<i<<" ";
    }
    std::cout<<std::endl;
}

and it displays

7 3 1 6 5

which seems to be the desired result.