임의의 삼중 항 알파벳의 단어를 추측

Question

나는이 문제를 해결하면서 아직 전체 해결책을 찾아 내지 못했습니다. (출처 : http://www.careercup.com/question?id=5678056593162240)

함수

getRandomTripplet() 문자열에서 문자의 임의의 삼중를 반환

을 감안할 때. 당신은 이 함수에 대한 호출을 사용하여 문자열을 알지 못한다면, 정확히 문자열을 추측해야합니다. 문자열의 길이도 제공됩니다.

는 문자열이 기능을 helloworld를하고 있다고하자 getRandomTriplet 것이다

함수가 문자의 상대적 순서를 유지 WLD owo

HLO의 HEW 같은 반환 것들. 그래서 결코 돌아 오지 않을 것입니다

ohl 왜냐하면 h는 문자열에서 o 앞에 있기 때문입니다. w가 e 이후입니다.

문자열이 알려져 있지 않습니다. 문자열의 길이 만 제공됩니다.

내 접근 방식은 getRandomTripplet()을 1000 번 실행 한 다음 가장 높은 발생 횟수 (확률> 1/10)를 가져 와서 중복 문자를 찾습니다.

올바른 경로에 있습니까?

도움 주셔서 감사합니다. 건배!

Answer 1

확률 론적 해결 방법을 찾지 못한 후에 올바른 결과를 이끌어 낼 수있는 무차별 대입 방식을 생각해 냈습니다. 일부 문자열의 경우 전체 상태 공간이 매우 크지 만 결국 알고리즘이 수렴 할 것입니다.

아마도 가장 효율적인 솔루션은 아니지만 트릭을 수행하는 것 같습니다. 아래의 코드는 상당히 최적화 될 수 있지만 예제로 충분해야합니다.

#include <iostream> 
#include <set> 
#include <functional> 

#include <boost/random/mersenne_twister.hpp> 
#include <boost/random/uniform_int_distribution.hpp> 

// the input string for the random generator 
static const std::string input("hello_world"); 
// an "empty" character (something not present in the input string) 
static const char empty = '?'; 
// a constant with the input length (the only known fact about the input in the algorithm) 
static const unsigned length = input.length(); 

// randomization algorithm returning triplets 
std::string randomTriplet() { 
    static boost::random::mt19937 gen; 
    static boost::random::uniform_int_distribution<> dist(0, input.length()-1); 

    std::set<unsigned> indices; 
    while(indices.size() < 3) 
     indices.insert(dist(gen)); 

    std::string result; 
    for(auto i : indices) 
     result.push_back(input[i]); 
    return result; 
} 

// runs a functor for all possible combinations of input triplet acc to the rules 
void allCombinations(const std::string& triplet, const std::function<void(const std::string&)>& functor) { 
    for(unsigned a=0;a<length-2;++a) 
     for(unsigned b=a+1;b<length-1;++b) 
      for(unsigned c=b+1;c<length;++c) { 
       std::string tmp(length, empty); 
       tmp[a] = triplet[0]; 
       tmp[b] = triplet[1]; 
       tmp[c] = triplet[2]; 

       functor(tmp); 
      } 
} 

// tries to merge two strings, and returns an empty string if it is not possible 
std::string putTogether(const std::string& first, const std::string& second) { 
    std::string result(length, empty); 

    for(unsigned a=0;a<length;++a) 
     if((first[a] == empty) || (first[a] == second[a])) 
      result[a] = second[a]; 
     else if(second[a] == empty) 
      result[a] = first[a]; 
     else if(first[a] != second[a]) 
      return std::string(); 

    return result; 
} 

// run a single iteration on a set of input states and a triplet 
std::set<std::string> iterate(const std::set<std::string>& states, const std::string& triplet) { 
    std::set<std::string> result; 

    // try all combinations on all states 
    for(auto& s : states) { 
     allCombinations(triplet, [&](const std::string& val) { 
      // and if merge is possible, insert it into the result 
      const std::string together = putTogether(s, val); 
      if(!together.empty()) 
       result.insert(together); 
     }); 
    }; 

    return result; 
} 

int main(int argc, char*argv[]) { 
    // the current state space (all possible strings given the observations so far) 
    std::set<std::string> states; 

    // initialisation - take the first triplet and generate all combinations of this triplet 
    allCombinations(randomTriplet(), [&](const std::string& val) { states.insert(val); }); 

    // iterate - the number of iterations is rather arbitrary. We cannot stop when the solution 
    // count is 1, because some input strings (like "hello world", where the double l and o 
    // are the problem) don't have a unique solution 
    for(unsigned a=0;a<10000;++a) { 
     states = iterate(states, randomTriplet()); 
     std::cout << "\r" << "iteration #" << a << ", combinations count = " << states.size() << " " << std::flush; 

     // however, if we do find a single solution, we don't have to go on 
     if(states.size() == 1) 
      break; 
    } 
    std::cout << std::endl; 

    // print them all 
    for(const auto& i : states) 
     std::cout << i << std::endl; 

    return 0; 
} 

흥미롭게 "인 Hello_World"입력, 출력은 :

iteration #9999, combinations count = 6  
hello_world 
helol_world 
hlelo_world 
hleol_world 
lhelo_world 
lheol_world 

트리플 'L'더블 'O'캐릭터 관찰 방법을 통해서만 결정될 수 모호성을 제조 세자를 가진.