我遇到了这个问题,但我还没有找到完整的解决方案。
(来源:http://www.careercup.com/question?id=5678056593162240)
Given a function
getRandomTripplet()
which returns a random triplet of letters from a string. You don't
know the string using calls to this function you have to correctly
guess the string. the length of the string is also given.
Lets say the string is helloworld the function getRandomTriplet will
return things like
hlo hew wld owo
the function maintains the relative order of the letters. so it will
never return
ohl since h is before o in the string. owe since w is after e
The string is not known you are only given length of the string.
到目前为止,我的方法是运行 getRandomTripplet() 1000 次,然后通过获取出现次数最多的字符(概率 > 1/10)来查找重复字符。
我走在正确的轨道上吗?
感谢您的帮助。
干杯!
在未能生成概率解决方案之后,我想出了这种似乎能产生正确结果的蛮力方法。对于某些字符串,总状态空间相当大,但算法最终会收敛:)
这可能不是最有效的解决方案,但它确实可以解决问题。下面的代码可以优化很多,但作为示例应该足够了。
#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”字符会产生歧义,仅使用三个字符的观察方法无法确定。