Find the largest permutation less than a certain value

Question

Here is some programming problem that I cannot figure out how to do this.

For two integers aand bfind the largest permutation of digits a, which is smaller b.

Is it possible to use the function next_permutationin c++? Or should I use some form of dynamic programming to solve this problem?

I tried to check all permutations awith the next_permutation function, but since the size of integers can be up to 10 ^ 18, 18! too big to be feasible. Is there a way to shorten the time? If not, how should I use dynamic programming for this kind of problem?

I would really appreciate any help for this. Thanks guys so much!

Answer 1

You do not need to search for all combinations for this a.

Suppose that ais “peace” and b“hello”. You can find the largest character in awhich is less than or equal to the first character b. In this case, you will find "d" in a. This is the biggest character you can start with your permutations a, so you should start with it. Since the "d" is strictly smaller than the "h", you can simply rank all the remaining characters afrom largest to smallest, and you will get "dwrol".

, , a - "", b - "", a b. , a, 'l'. "w", "o", "r", "d" . , "like", "d", "ldwro".

Edit:

( ) . a , b, a , b (, 0 a). , . a , b, a, a b. , , .

a 0s, , 0 , b, .

Answer 2

. .

( ):

, , a, , a , b.

, . , .

• b, .

• a b , , . , .

• b a, b, a - .

• a b, b ( ). , a , b. , , , .

Answer 3

Agree with previous answers Here is a snippet of code that represents the view

#include<iostream>
#include <set>
#include <string>
#include <algorithm>

    std::string greatest_permutation(const std::string &s, const std::string &limit) {
        std::string result;
        std::set<char> bag;
        std::copy(s.begin(), s.end(),
             std::insert_iterator<std::set<char> >(bag, bag.begin()));
        for (int j=0; j<limit.size(); ++j) {
            std::set<char>::iterator i = bag.upper_bound(limit[j]);
            if (i == bag.begin()) // no more chars available
                return result;
            else
                result += *--i;
            bag.erase(i);
        }
    return result;
    }

    int main() {
        std::cout<<
        greatest_permutation("abcdefghi", "cfhuiigwuioiiom")
        <<std::endl;
    }