字符串连接以生成互补删除

Question

这个问题是 post 的一个小改动。给定一个字符串，我想生成一个字符串向量删除 x 次。例如：

String a = "ABCD";
int x = 2;
//vector<string> residue = generate(a, x);
//vector residue would have the following elements: 
//"AB", "BC", "CD", "AC" "AD", "BD"

完成后，我想生成第二个包含带有其他 2 个字符的字符串的字符串向量删除。但是，代替删除，我想插入 .。例如：

//vector<string> residue2 would have the following elements:
//"..CD", "A..D", "AB..", ".B.D", ".BC.", "A.C."

这是我为 x = 1 所做的尝试。但是，我无法生成第二个字符串或概括为 x 等于任何数字。

vector<int> orignal; 
for(int i = 1; i <= 5; i++) original.push_back(i);
vector<int> data2;
for(int p1 = 0; p1 < length; p1++){
    auto data1 = original
    data1.erase(data1.begin()+p1);
    for(int p2 = 0; p2 < length; p2++){
        data2 = original;
        if(p2 != p1)
            data2.erase(data2.begin()+p2);
        //do stuff
    }
}

编辑：我要实现的是：（x=1可以参考我的伪代码）假设 original = {1, 2, 3}。然后在外 for-loop、data1 = {2,3} 和 data2 = {1,2,3} 的第一次迭代中，然后是 data2={1,2,.}。在外部 for-loop、data1 = {1,3} 和 data2 = {1,2,.} 的第二次迭代中，然后是 data2={.,2,3}。然后再持续 data1 = {1,2} 一次。现在这是我只从原始元素中删除一个元素的时候。但是，我想对此进行概括，以便 data1 将对 x < 长度进行任何 x 删除。因此，data2 也将删除 x，但它会有条不紊地删除 data1 中尚未删除的元素。

Answer 1

假设你的字符串长度是n。且 x<=n.

所以用 x 1 和 n-x 0 创建一个字符串。

string your_string="...";
for(int i=0;i<n;i++)
     ss+=(i<=n-x-1)?"0":"1";


do
{
   string temp="";
   for(int i=0;i<=n-1;i++)
     if(ss[i]=='1')
        temp+=".";
     else
        temp+=your_string[i];
   /*  process temp..*/
}
while(next_permutation(ss.begin(),ss.end())

示例

for n=3 x=2
"ABC"
A..  011
.B.  101
..C  110

Answer 2

您可以使用 std::next_permutation() 循环遍历一组 bool（表示输入或输出）的所有排列。例如

#include <string>
#include <vector>
#include <algorithm>

std::vector<std::string> generate(std::string const&str, std::size_t x)
{
  const auto size = str.size();
  std::vector<bool> perm(size);
  for(std::size_t i=0; i!=size; ++i)
    perm[i] = i>=x;
  std::vector<std::string> result;
  do {
    auto copy = str;
    for(std::size_t i=0; i!=size; ++i)
      if(!perm[i]) copy[i]='.';
    result.push_back(std::move(copy));
  } while(std::next_permutation(perm.begin(),perm.end()));
  return result;
}

例如 str="ABCDE" x=2 我们得到

{"..CDE",".B.DE",".BC.E",".BCD.","A..DE","A.C.E","A.CD.","AB..E","AB.D.","ABC.."}

字符串连接以生成互补删除

String concatenation to generate complementary removals

c++

string

algorithm

vector

combinatorics