Я хочу получить все слова определенной длины / алфавита, которые имеют минимальное расстояние Хемминга между собой.
Я не математик, поэтому я пытаюсь показать пример, чтобы прояснить, что мне нужно.
Word Length L = 4
Word Alphabet A = {0,1}
Word Alphabet Size |A| = 2
Word Min. Hamming Dist. H = 2
Первое слово
w0 = {0,0,0,0}
Теперь другие слова могут быть:
w1 = {0,0,1,1}
w2 = {1,1,0,0}
И расстояния Хэмминга
Hamming(w0,w1) = 2 >= H
Hamming(w0,w2) = 2 >= H
Hamming(w1,w2) = 4 >= H
Как видите, все расстояния Хэмминга равны или больше H.
Для моей цели мне понадобится L=512 and A={0,1} and |A|=2 and H=70
,
Как я могу рассчитать все это без грубой силы / проб и ошибок?
Ниже приведен некоторый некрасивый быстрый код взлома, который в конечном итоге медленный. Как быстро получить эту молнию?
// std header(s)
#include <array>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <iterator>
#include <random>
#include <chrono>
#include <boost/iterator/zip_iterator.hpp>
#include <boost/tuple/tuple.hpp>
#include <boost/tuple/tuple_comparison.hpp>
#include <bitset>
#include <fstream>
#include <iostream>
class Hamming {
public:
Hamming(int & _distance) : distance_(_distance) {};
void operator() ( boost::tuple<int, int> const & words) {
if(boost::get<0>(words)!=boost::get<1>(words)) {
std::bitset<4> n=boost::get<0>(words);
std::bitset<4> m=boost::get<1>(words);
distance_+=(n ^ m).count();
}
}
private:
int & distance_;
};int main(int argc,char** argv) {
const int arraysize=61;
std::array<int,arraysize> a;
int distance=0;
int num;
std::cout << "Input number of bag_words"<<std::endl;;
std::cin>>num;
std::vector<std::array<int, arraysize>> bag;
Hamming myobject(distance);
////
std::mt19937 mt(std::chrono::high_resolution_clock::now().time_since_epoch().count());
std::uniform_int_distribution<int> d(0, 255);
std::generate(a.begin(),a.end(),[&]{return d(mt);});
bag.push_back(a);
int counter=1;
while (counter<num) {
std::generate(a.begin(),a.end(),[&]{return d(mt);});
int test=0;
distance=0;
for (int i=0 ; i<counter ; i++) {
std::for_each(
boost::make_zip_iterator(
boost::make_tuple(a.begin(), bag[i].begin())
),
boost::make_zip_iterator(
boost::make_tuple(a.end(), bag[i].end())
),
Hamming(distance)
);
if(distance>10) {
++test;
}
else break;
}
if (test==counter) {
bag.push_back(a);
++counter;
}
}
std::cout << std::endl;
std::ofstream myfile ("example.txt");
if (myfile.is_open()) {
for(int i = 0; i < counter; i ++) {
for (int j=0 ; j<arraysize ; j++) {
myfile << bag[i][j] << " " ;
}
myfile << "\n";
}
myfile.close();
}
else std::cout << "Unable to open file";
}
Задача ещё не решена.
Других решений пока нет …