Звучит как тяжелая проблема.
Если вы используете size_t для индекса перестановки, ваши строки будут ограничены 32 или 64 символами, в противном случае вам понадобится большее целое число для индекса перестановки. Поэтому вы можете переключаться со строк на битовые маски size_t.
Таким образом, ваш алгоритм больше не зависит от строки, вы находите i-ую битовую маску, XOR it (оператор ^ в C ++) с битовой маской входной строки, и вы получаете свой результат. Сложнее всего найти i-ю битовую маску, но таким образом, то есть без использования строк во внутренних циклах алгоритма, код будет намного быстрее (на несколько порядков).
Теперь самое сложное - как найти маску. В общем случае единственный алгоритм, который я могу придумать, - это расширенный поиск, возможно, с запоминанием производительности. Это будет быстро для небольших индексов перестановки, но медленно для больших.
Если вы знаете свой вес во время компиляции, вы можете предварительно вычислить индексы в дереве поиска, но лучше всего это делать вне C ++, очень сложно использовать шаблонное метапрограммирование для сложных алгоритмов, подобных этому.
P.S. Есть один особый случай, который может сработать для вас. Сортируйте весовые коэффициенты и проверьте, верно ли следующее weights[N] == weights[N-1] || weights[N] >= sum( weights[0 .. N-1] для всех 1
Кстати, веса, которые у вас есть в вопросе, удовлетворяют этому условию, потому что 1> = 0, 3> = 0 + 1 и 5> = 0 + 1 + 3, так что этот простой алгоритм будет работать нормально для ваших конкретных весов.
Обновление: Вот полное решение. Он печатает немного другой результат, чем ваш образец, например, в вашем примере у вас есть «1011», а затем «1111», мой код будет печатать «1011» сразу после «1111», но их расстояние будет таким же, т. е. мой алгоритм все еще работает в порядке.
#include <string>
#include <vector>
#include <algorithm>
#include <stdio.h>
struct WeightWithBit
{
size_t weight, bit;
};
// Sort the weights while preserving the original order in the separate field
std::vector<WeightWithBit> sortWeights( const std::vector<size_t>& weights )
{
std::vector<WeightWithBit> sorted;
sorted.resize( weights.size() );
for( size_t i = 0; i < weights.size(); i++ )
{
sorted[ i ].weight = weights[ i ];
sorted[ i ].bit = ( (size_t)1 << i );
}
std::sort( sorted.begin(), sorted.end(), []( const WeightWithBit& a, const WeightWithBit& b ) { return a.weight < b.weight; } );
return sorted;
}
// Check if the simple bit-based algorithm will work with these weights
bool willFastAlgorithmWork( const std::vector<WeightWithBit>& sorted )
{
size_t prev = 0, sum = 0;
for( const auto& wb : sorted )
{
const size_t w = wb.weight;
if( w == prev || w >= sum )
{
prev = w;
sum += w;
continue;
}
return false;
}
return true;
}
size_t bitsFromString( const std::string& s )
{
if( s.length() > sizeof( size_t ) * 8 )
throw std::invalid_argument( "The string's too long, permutation index will overflow" );
size_t result = 0;
for( size_t i = 0; i < s.length(); i++ )
if( s[ i ] != '0' )
result |= ( (size_t)1 << i );
return result;
}
std::string stringFromBits( size_t bits, size_t length )
{
std::string result;
result.reserve( length );
for( size_t i = 0; i < length; i++, bits = bits >> 1 )
result += ( bits & 1 ) ? '1' : '0';
return result;
}
// Calculate the permitation. Index is 0-based, 0 will return the original string without any changes.
std::string permitation( const std::string& str, const std::vector<WeightWithBit>& weights, size_t index )
{
// Reorder the bits to get the bitmask.
// BTW, if this function is called many times for the same weights, it's a good idea to extract just the ".bit" fields and put it into a separate vector, memory locality will be slightly better.
size_t reordered = 0;
for( size_t i = 0; index; i++, index = index >> 1 )
if( index & 1 )
reordered |= weights[ i ].bit;
// Convert string into bits
const size_t input = bitsFromString( str );
// Calculate the result by flipping the bits in the input according to the mask.
const size_t result = input ^ reordered;
// Convert result to string
return stringFromBits( result, str.length() );
}
int main()
{
const std::vector<size_t> weights = { 1, 0, 3, 5 };
using namespace std::literals::string_literals;
const std::string theString = "1101"s;
if( weights.size() != theString.length() )
{
printf( "Size mismatch" );
return 1;
}
if( weights.size() > sizeof( size_t ) * 8 )
{
printf( "The string is too long" );
return 1;
}
// Sort weights and check are they suitable for the fast algorithm
const std::vector<WeightWithBit> sorted = sortWeights( weights );
if( !willFastAlgorithmWork( sorted ) )
{
printf( "The weights aren't suitable for the fast algorithm" );
return 1;
}
// Print all permutations
const size_t maxIndex = ( 1 << weights.size() ) - 1;
for( size_t i = 0; true; i++ )
{
const std::string p = permitation( theString, sorted, i );
printf( "%zu: %s\n", i, p.c_str() );
if( i == maxIndex )
break; // Avoid endless loop when the string is exactly 32 or 64 characters.
}
return 0;
}