Как быстро сгенерировать строки по маске?

196

05 апреля 2021, 08:00

Стоит задача сгенерировать строки со случайной вставкой символа * в любое место строки. Максимум таких символов может быть в строке 4. Как сгенерировать все возможные вариации таких строк максимально быстро? У меня получилось только для одного *. Никак не додумаю как сделать для всех вариаций.

var lst = new List<string>();
var str = "приветмир";
var max = 4;
for (int i = 0; i < max; i++)
{
    for (int j = 0; j < str.Length; j++)
    {
        var s = ReplaceFirst(str, str[j].ToString(), "*");
    }
}
public static string ReplaceFirst(string text, string search, string replace)
{
    int pos = text.IndexOf(search);
    if (pos < 0)
    {
        return text;
    }
    return text.Substring(0, pos) + replace + text.Substring(pos + search.Length);
}

Должно получиться

*риветмир
п*иветмир
пр*ветмир
при*етмир
прив*тмир
приве*мир
привет*ир
приветм*р
приветми*
**иветмир
*р*ветмир
*ри*етмир
....

Answer 1

Например, так

var str = "приветмир";
var sb = new StringBuilder(str);
for(var i=0; i<str.Length; i++)
{
    var c = sb[i];
    sb[i] = '*';
    Console.WriteLine(sb.ToString());
    sb[i] = c;
}

Вывод

*риветмир
п*иветмир
пр*ветмир
при*етмир
прив*тмир
приве*мир
привет*ир
приветм*р
приветми*

Генерируем от 0 до 4 зведзочек

public IEnumerable<string> Generate(StringBuilder sb, int index, int count)
{
    if (index == sb.Length)
    {
        yield return sb.ToString();
    }
    else if (count == 0)
    {
        yield return sb.ToString();
    }
    else
    {
        foreach (var s in Generate(sb, index + 1, count)) yield return s;
        var c = sb[index];
        sb[index] = '*';
        foreach (var s in Generate(sb, index + 1, count - 1)) yield return s;
        sb[index] = c;
    }
}

Как использовать

var str = "приветмир";
var sb = new StringBuilder(str);
foreach(var s in Generate(sb, 0, 4))
    Console.WriteLine(s);

Вывод

приветмир
приветми*
приветм*р
приветм**
привет*ир
привет*и*
привет**р
привет***
приве*мир
приве*ми*
приве*м*р
приве*м**
приве**ир
приве**и*
приве***р
приве****
прив*тмир
прив*тми*
прив*тм*р
прив*тм**
прив*т*ир
прив*т*и*
прив*т**р
прив*т***
прив**мир
прив**ми*
прив**м*р
прив**м**
прив***ир
прив***и*
прив****р
при*етмир
при*етми*
при*етм*р
при*етм**
при*ет*ир
при*ет*и*
при*ет**р
при*ет***
при*е*мир
при*е*ми*
при*е*м*р
при*е*м**
при*е**ир
при*е**и*
при*е***р
при**тмир
при**тми*
при**тм*р
при**тм**
при**т*ир
при**т*и*
при**т**р
при***мир
при***ми*
при***м*р
при****ир
пр*ветмир
пр*ветми*
пр*ветм*р
пр*ветм**
пр*вет*ир
пр*вет*и*
пр*вет**р
пр*вет***
пр*ве*мир
пр*ве*ми*
пр*ве*м*р
пр*ве*м**
пр*ве**ир
пр*ве**и*
пр*ве***р
пр*в*тмир
пр*в*тми*
пр*в*тм*р
пр*в*тм**
пр*в*т*ир
пр*в*т*и*
пр*в*т**р
пр*в**мир
пр*в**ми*
пр*в**м*р
пр*в***ир
пр**етмир
пр**етми*
пр**етм*р
пр**етм**
пр**ет*ир
пр**ет*и*
пр**ет**р
пр**е*мир
пр**е*ми*
пр**е*м*р
пр**е**ир
пр***тмир
пр***тми*
пр***тм*р
пр***т*ир
пр****мир
п*иветмир
п*иветми*
п*иветм*р
п*иветм**
п*ивет*ир
п*ивет*и*
п*ивет**р
п*ивет***
п*иве*мир
п*иве*ми*
п*иве*м*р
п*иве*м**
п*иве**ир
п*иве**и*
п*иве***р
п*ив*тмир
п*ив*тми*
п*ив*тм*р
п*ив*тм**
п*ив*т*ир
п*ив*т*и*
п*ив*т**р
п*ив**мир
п*ив**ми*
п*ив**м*р
п*ив***ир
п*и*етмир
п*и*етми*
п*и*етм*р
п*и*етм**
п*и*ет*ир
п*и*ет*и*
п*и*ет**р
п*и*е*мир
п*и*е*ми*
п*и*е*м*р
п*и*е**ир
п*и**тмир
п*и**тми*
п*и**тм*р
п*и**т*ир
п*и***мир
п**ветмир
п**ветми*
п**ветм*р
п**ветм**
п**вет*ир
п**вет*и*
п**вет**р
п**ве*мир
п**ве*ми*
п**ве*м*р
п**ве**ир
п**в*тмир
п**в*тми*
п**в*тм*р
п**в*т*ир
п**в**мир
п***етмир
п***етми*
п***етм*р
п***ет*ир
п***е*мир
п****тмир
*риветмир
*риветми*
*риветм*р
*риветм**
*ривет*ир
*ривет*и*
*ривет**р
*ривет***
*риве*мир
*риве*ми*
*риве*м*р
*риве*м**
*риве**ир
*риве**и*
*риве***р
*рив*тмир
*рив*тми*
*рив*тм*р
*рив*тм**
*рив*т*ир
*рив*т*и*
*рив*т**р
*рив**мир
*рив**ми*
*рив**м*р
*рив***ир
*ри*етмир
*ри*етми*
*ри*етм*р
*ри*етм**
*ри*ет*ир
*ри*ет*и*
*ри*ет**р
*ри*е*мир
*ри*е*ми*
*ри*е*м*р
*ри*е**ир
*ри**тмир
*ри**тми*
*ри**тм*р
*ри**т*ир
*ри***мир
*р*ветмир
*р*ветми*
*р*ветм*р
*р*ветм**
*р*вет*ир
*р*вет*и*
*р*вет**р
*р*ве*мир
*р*ве*ми*
*р*ве*м*р
*р*ве**ир
*р*в*тмир
*р*в*тми*
*р*в*тм*р
*р*в*т*ир
*р*в**мир
*р**етмир
*р**етми*
*р**етм*р
*р**ет*ир
*р**е*мир
*р***тмир
**иветмир
**иветми*
**иветм*р
**иветм**
**ивет*ир
**ивет*и*
**ивет**р
**иве*мир
**иве*ми*
**иве*м*р
**иве**ир
**ив*тмир
**ив*тми*
**ив*тм*р
**ив*т*ир
**ив**мир
**и*етмир
**и*етми*
**и*етм*р
**и*ет*ир
**и*е*мир
**и**тмир
***ветмир
***ветми*
***ветм*р
***вет*ир
***ве*мир
***в*тмир
****етмир