如何排列二进制字符串以最小化它们之间的距离

例如，我有一个权重数组

[1, 0, 3, 5]

两个字符串之间的距离定义为不同位的权重总和，如下所示：

size_t distance(const std::string& str1, const std::string& str2, const std::vector<size_t>& weights) {
size_t result = 0;
for (size_t i = 0; i < str1.size(); ++i) {
if (str1[i] != str2.at(i))
result += weights.at(i);
}
return result;
}

和起始字符串，例如

'1101'

我需要以与原始字符串距离最低的字符串先行的方式生成排列，如下所示：

'1001'  # changed bits: 2nd. Because it has lowest weight. Distance is 0
'0101'  # changed bits: 1st.                               Distance is 1
'0001'  # changed bits: 1st, 2nd.                          Distance is 1
'1011'  # changed bits: 2nd, 3rd.                          Distance is 3
'1111'  # changed bits: 3rd.                               Distance is 3
'0111'  # changed bits: 1st, 3rd.                          Distance is 4
'0011'  # changed bits: 1st, 2nd, 3rd.                     Distance is 4
'1100'  # changed bits: 4th.                               Distance is 5
'1000'  # changed bits: 2nd, 4th.                          Distance is 5
'0100'  # changed bits: 1st, 4th.                          Distance is 6
'0000'  # changed bits: 1st, 2nd, 4th.                     Distance is 6
'1110'  # changed bits: 3rd, 4th.                          Distance is 8
'1010'  # changed bits: 2nd, 3rd, 4th.                     Distance is 8
'0110'  # changed bits: 1st, 3nd, 4th.                     Distance is 9
'0010'  # changed bits: 1st, 2nd, 3rd, 4th.                Distance is 9

我不需要代码，我只需要一个算法，它获取长度为 N 的字符串、长度和 i 相同的权重数组作为输入并生成第 i 个排列，而无需生成整个列表并对其进行排序。

听起来像是难题。

如果使用 size_t 作为排列索引，则字符串将限制为 32 或 64 个字符，否则排列索引需要更大的整数。因此，可以从字符串切换到size_t位掩码。

这样，您的算法不再依赖于字符串，您可以找到第 i 个位掩码，XOR it(^C++ 中的运算符)与输入字符串位掩码，然后得到结果。困难的部分是找到第 i 个位掩码，但这样，即在算法的内部循环中不使用字符串，代码将快得多(一个数量级)。

现在困难的部分是如何找到面具。对于一般情况，我能想到的唯一算法是广泛的搜索，也许是针对性能的记忆。这对于小的排列索引来说会很快，但对于大的排列索引来说会很慢。

如果你在编译时知道你的权重，你可以预先计算索引到搜索树中，但最好在C++之外完成，很难将模板元编程用于像这样的复杂算法。

附言有一种特殊情况可能适合您。对权重进行排序，并检查以下内容是否成立weights[N] == weights[N-1] || weights[N] >= sum( weights[0 .. N-1]对于所有 1

顺便说一句，您在问题中的权重满足该条件，因为 1>=0、3>=0+1 和 5>=0+1+3，因此这个简单的算法适用于您的特定权重。

更新：这是一个完整的解决方案。它打印的结果与您的样本略有不同，例如在您的示例中，您有"1011"然后是"1111"，我的代码将在"1111"之后立即打印"1011"，但它们的距离是相同的，即我的算法仍然工作正常。

#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: %sn", i, p.c_str() );
if( i == maxIndex )
break;  // Avoid endless loop when the string is exactly 32 or 64 characters.
}
return 0;
}

在现代C++中，执行所要求操作的方法是使用std::bitset表示所有可能的位多集，然后用比较器函子结构包装distance()以调用std::sort()。我强调可能的位多重集，而不是排列，因为后者只允许改变顺序。然后，您的代码将如下所示：

#include <string>
#include <array>
#include <cmath>
#include <bitset>
#include <vector>
#include <algorithm>
#include <iostream>
constexpr size_t BITSET_SIZE = 4;
size_t distance(const std::string& str1, const std::string& str2, const std::array<size_t, BITSET_SIZE>& weights) {
size_t result = 0;
for (size_t i = 0; i < str1.size(); ++i) {
if (str1[i] != str2.at(i))
result += weights.at(i);
}
return result;
}
struct of_lesser_distance
{
const std::bitset<BITSET_SIZE>& originalBitSet;
const std::array<size_t, BITSET_SIZE>& distanceVec;
inline bool operator() (const std::bitset<BITSET_SIZE>& lhs, const std::bitset<BITSET_SIZE>& rhs)
{
return distance(originalBitSet.to_string(), lhs.to_string(), distanceVec) < distance(originalBitSet.to_string(), rhs.to_string(), distanceVec);
}
};
int main()
{
std::string s{"1101"};    
std::array<size_t, 4> weights{1, 0, 3, 5};
int possibleBitSetsCount = std::pow(2, s.length());
std::vector<std::bitset<BITSET_SIZE>> bitSets;
// Generates all possible bitsets
for (auto i = 0; i < possibleBitSetsCount; i++)
bitSets.emplace_back(i);
// Sort them according to distance
std::sort(bitSets.begin(), bitSets.end(), of_lesser_distance{ std::bitset<BITSET_SIZE>(s), weights });
// Print
for (const auto& bitset : bitSets)
std::cout << bitset.to_string().substr(BITSET_SIZE - s.length(), s.length()) << " Distance: " << distance(s, bitset.to_string(), weights) << "n";
}

输出：

1001 Distance: 0
1101 Distance: 0
0001 Distance: 1
0101 Distance: 1
1011 Distance: 3
1111 Distance: 3
0011 Distance: 4
0111 Distance: 4
1000 Distance: 5
1100 Distance: 5
0000 Distance: 6
0100 Distance: 6
1010 Distance: 8
1110 Distance: 8
0010 Distance: 9
0110 Distance: 9

现场版本在这里。

请注意：这样，您最好更改distance()以处理std::bitset而不是std::strings，因为它可以节省所有这些不必要的转换。

我

不需要代码，我只需要一个算法

对我来说，提供代码更容易，但如果你想要其他东西，请告诉我。

这个问题无法有效解决。它可以多项式简化为子集和问题，它本身就是一个NP完全问题。

如果您不介意详尽的解决方案，只需迭代与基字符串长度相同的所有可能的字符串，并使用distance来计算它们的距离并跟踪最大i距离。

由于对问题的误解，原始错误答案：
听起来像一个简单的问题。由于您已经必须生成所有这些字符串，因此您的解决方案相对于基本字符串将是指数级的(在空间和时间上)。你基本上不受约束。

你可以尝试类似[^1]：
1.生成所有可能与基字符串长度相同的字符串。这很简单。只需从 0 循环到 (2^|base_str|-1)，并使用sprintf(&strs[loop_counter]"%b", loop_counter)
2.使用qsort对strs进行排序，并使用distance作为编译器。类似于qsort(str, 1 << strlen(base_str)-1, sizeof(char*), comp)，其中comp是一个接受两个字符串的函数，如果第一个字符串的 base_str 距离小于第二个字符串，则返回 -1，如果两者的距离相等，则返回 0，如果第一个参数比第二个参数离base_str更远，则返回 1。

^[1]我是一个C，而不是C++程序员，所以我确信还有其他(也许更好)的方法可以完成我在C++中提出的建议，但我的例子是用C语言的。

如果你只想要第 i 个排列，那么你只需要查看权重。

如果权重是反向排序的，比如说[5,3,1,0]并且你想要第 5 次渗透，那么您需要在二进制中翻转0, 1, 0, 15 = 0101。

因此，您需要从权重到原始索引的非常小的映射。然后，从大到小排序，根据 N 的二进制表示获取第 N 个排列，并翻转原始字符串的映射位。

相关内容

最新更新

热门标签：