0

Есть такая заготовка: (аа) (,|;) (аа|вв) (;|,|) (гв|аб вб)
Надо, сохраняя последовательность, перебрать все возможные варианты, которые образуются с помощью разделителя "|". Подскажите, как называется такой алгоритм, как его реализовать на c#, или ещё на каком-то языке?

Вот что должно получится из заготовки:
(аа) (,) (аа) (;) (гв)
(аа) (;) (аа) (;) (гв)
(аа) (,) (вв) (;) (гв)
(аа) (,) (аа) (,) (гв)
(аа) (,) (аа) () (гв)
(аа) (,) (аа) (;) (аб вб)
...
и т.д.

6
  • Слишком мало информации для решения. Объясните подробнее и укажите контекст задачи. Преобразования во что? Пока что могу посоветовать конструкции для работы с регулярными выражениями.
    – Steve
    20 дек 2015 в 12:47
  • добавьте примеры входных и выходных данных
    – Grundy
    20 дек 2015 в 14:06
  • Дополнил выходные данные. Строка это и есть входные данные. Нужно получить список всех возможных строк. Контекст задачи - получение всех вариантов шаблонов, которые потом будут по одному использованы для сравнения.
    – Maksim
    20 дек 2015 в 15:12
  • Что значит «скобки для наглядности»? Покажите ваш реальный синтаксис. Например: какую роль играют пробелы (опишите максимально точно).
    – VladD
    20 дек 2015 в 15:41
  • Предполагается, что это будут элементы списка, можно со скобками можно без. У меня со скобками. Если точно, то все что в скобках - элементы списка.
    – Maksim
    20 дек 2015 в 15:42

2 ответа 2

1

Такой алгоритм называется "генератор анкоров" (Anchor Generator). Вот пример для рэндомного получения результата (не генерация списка всех вариантов), где разделитель вместо () будет [[...]] и нет вложенности анкоров

internal class AnchorGenerator
{
    private readonly Random _random = RandomFactory.Create();
    private readonly Regex _regex = new Regex(@"\[\[([^\[\[]*)\]\]");

    public string Generate(string template)
    {
        var matches = _regex.Matches(template);

        if (matches.Count == 0)
            return template;

        foreach (Match match in matches)
        {
            var tpl = match.Groups[1].Value;
            var variants = tpl.Split('|');

            var variant = variants[_random.Next(variants.Length)];

            template = template.ReplaceFirstOccurrence(match.Value, variant);
        }

        return template;
    }
}

где

public static string ReplaceFirstOccurrence(this string s, string oldValue, string newValue)
    {
        int i = s.IndexOf(oldValue, StringComparison.Ordinal);
        if (i == -1) return s;
        return s.Remove(i, oldValue.Length).Insert(i, newValue);
    }
0

Нашел алгоритм на JS, переделал. Если кто-то прокомментирует реализацию (по-моему, достаточно запутано получилось) буду благодарен.

    List<string> resultList = new List<string>();
    List<int> counters1;
    private string strRes;
    private List<List<string>> result;
    public List<string> GetColll(string[] shab)
    {
        foreach (var itemShab in shab)
        {
            counters1 = new List<int>();
            result = new List<List<string>>();

            List<string> pattern = Regex.Split(itemShab, @"\(").ToList();
            List<string> vars = new List<string>();
            List<string> part;


               for (int i = 0; i < pattern.Count; i++)
               {
                //отсеиваем пустую строку
               if (pattern[i].Contains(@")"))
               {
                   part = pattern[i].Split(new char[] {')'},StringSplitOptions.RemoveEmptyEntries).ToList();
                   foreach (var prt in part)
                   {
                        if (prt.Contains(@"|"))
                        {
                            vars = prt.Split(new char[] { '|' }).ToList();
                            result.Add(vars);
                        }
                        else
                        {
                            List<string> partList = new List<string>();
                            partList.Add(prt);
                            result.Add(partList);
                        }

                    }


               }

            }
            CreateCounters();

            OnStep();
        }

        return null;
    }


    void CreateCounters()
    {
        List<int> counters = new List<int>();
        for (int i = 0; i < result.Count; i++)
        {
            counters.Add(0);
        }
        counters1 = counters;
    }

    private bool IsCounters()
    {
        int i = counters1.Count - 1;
        while (i >= 0)
        {
            if (result[i].Count - 1 > counters1[i])
            {
                counters1[i]++;
                return true;
            }
            counters1[i] = 0;
            i -= 1;
        }
        return false;
    }

    private void OnStep()
    {
        int len = counters1.Count;
        int i;
        string part;
        List <string> phrase = new List<string>();

        for (i = 0; i < len; i += 1)
        {
            part = result[i][counters1[i]];
            if (part != null)
            {
                phrase.Add(part);
            }
        }
        strRes = string.Join("", phrase.ToArray());
        resultList.Add(strRes);
        if (IsCounters())
        {
            OnStep();
        }
    }

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.