Sounds like hard problem.
If you are using size_t for permutation index, your strings will be limited to 32 or 64 characters, otherwise you’ll need larger integer for permutation index. Therefore, you can switch from strings to size_t bitmasks.
This way your algorithm no longer depends on the string, you find i-th bitmask, XOR it (^ operator in C++) with the input string bitmask, and you get your result. The hard part is finding i-th bitmask but this way, i.e. without using strings in the inner loops of the algorithm, the code will be much faster (an orders of magnitude).
Now the hard part is how to find the mask. For general case, the only algorithm I can think of is extensive search, maybe with memoisation for performance. This will be fast for small permutation indices but slow for large ones.
If you know your weights at compile-time, you can precompute indices into a search tree but it’s best done outside C++, it’s very hard to use template metaprogramming for complex algorithms like this one.
P.S. There’s one special case that might work for you. Sort weights, and check whether the following is true weights[N] == weights[N-1] || weights[N] >= sum( weights[0 .. N-1] for all 1<N<length, you only need a single loop over the sorted weights to check that. If it’s true for all weights, and also all weights are non-negative, the solution is trivially simple, and the performance will be very fast, just treat index as a XOR bitmask. The only thing you need to do, reorder bits in the index to match the order of the weights array that was changed as the result of sorting them. For your weights, switch first and second bits because the sorted order is [0,1,3,5].
BTW, the weights you have in the question satisfy that condition, because 1>=0, 3>=0+1 and 5>=0+1+3, so this simple algorithm will work OK for your particular weights.
Update: here's a complete solution. It prints slightly different result than your sample, e.g. in your example you have '1011' then '1111' , my code will print '1011' immediately after '1111' but their distance is the same, i.e. my algorithm still works OK.
#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;
}
