Найти все возможные комбинации слов с дефисом и без них

Question

Для строки, которая может иметь ноль или более дефисов, мне нужно извлечь всевозможные возможности с помощью дефисов и без них.

Например, строка «A-B» приведет к «A-B» и «AB» (две возможности).

Строка «A-B-C» приведет к «A-B-C», «AB-C», «A-BC» и «ABC» (четыре возможности).

Строка «ABCD» приведет к «ABCD», «AB-CD», «A-BC-D», «AB-CD», «AB-CD», «ABC-D», «A -BCD "и" ABCD "(восемь возможностей).

... и т.д., и т.д.

Я экспериментировал с некоторыми вложенными циклами, но не был в состоянии получить в любом месте вблизи желаемого результата. Я подозреваю, что мне нужно что-то рекурсивное, если нет какого-то простого решения, которое я пропускаю.

NB. Это необходимо для создания SQL-запроса (стыдно, что SQL Server не имеет соответствия шаблону REGEXP MySQL).

Вот одна попытка, над которой я работал. Это может сработать, если я сделаю это рекурсивно.

string keyword = "A-B-C-D"; 

List<int> hyphens = new List<int>(); 

int pos = keyword.IndexOf('-'); 
while (pos != -1) 
{ 
    hyphens.Add(pos); 
    pos = keyword.IndexOf('-', pos + 1); 
} 

for (int i = 0; i < hyphens.Count(); i++) 
{ 
    string result = keyword.Substring(0, hyphens[i]) + keyword.Substring(hyphens[i] + 1); 

    Response.Write("<p>" + result); 
} 

A B C D - слова различной длины.

Answer 1

Вы должны быть в состоянии отслеживать каждую позицию дефис, и в основном говорят, что его либо есть, либо нет. Прокрутите все комбинации, и вы получите все свои строки. Я нашел самый простой способ отслеживания он использует бинарный, так как его легко добавить те с Convert.ToInt32

Я придумал это:

string keyword = "A-B-C-D"; 
string[] keywordSplit = keyword.Split('-'); 
int combinations = Convert.ToInt32(Math.Pow(2.0, keywordSplit.Length - 1.0)); 

List<string> results = new List<string>(); 

for (int j = 0; j < combinations; j++) 
{ 
    string result = ""; 
    string hyphenAdded = Convert.ToString(j, 2).PadLeft(keywordSplit.Length - 1, '0'); 
    // Generate string 
    for (int i = 0; i < keywordSplit.Length; i++) 
    { 
     result += keywordSplit[i] + 
        ((i < keywordSplit.Length - 1) && (hyphenAdded[i].Equals('1')) ? "-" : ""); 
    } 
    results.Add(result); 
} 

Answer 2

Я не уверен, что ваш вопрос полностью определен (т. Е. У вас есть что-то вроде A-BCD-EF-G-H?). Для «полного» дефиса строк (A-B-C-D -...- Z), что-то вроде этого нужно сделать:

string toParse = "A-B-C-D"; 
char[] toParseChars = toPase.toCharArray(); 
string result = ""; 
string binary; 
for(int i = 0; i < (int)Math.pow(2, toParse.Length/2); i++) { // Number of subsets of an n-elt set is 2^n 
    binary = Convert.ToString(i, 2); 
    while (binary.Length < toParse.Length/2) { 
     binary = "0" + binary; 
    } 
    char[] binChars = binary.ToCharArray(); 

    for (int k = 0; k < binChars.Length; k++) { 
     result += toParseChars[k*2].ToString(); 
     if (binChars[k] == '1') { 
      result += "-"; 
     } 
    } 
    result += toParseChars[toParseChars.Length-1]; 
    Console.WriteLine(result); 
} 

Идея заключается в том, что мы хотим создать двоичное слово для каждого возможного дефиса. Итак, если у нас есть A-B-C-D (три дефиса), мы создаем двоичные слова 000, 001, 010, 011, 100, 101, 110 и 111. Заметим, что если у нас есть n дефисов, нам нужны 2^n бинарных слов.

Затем каждое слово соответствует желаемому выходу, вставив дефис, где у нас есть слово «1» (000 -> ABCD, 001 -> ABC-D, 010 -> AB-CD и т. Д.). Я не тестировал вышеприведенный код, но это, по крайней мере, один из способов решения проблемы для полностью переносимых слов.

Отказ от ответственности: Я на самом деле не проверить код

Answer 3

Это работает для меня:

Func<IEnumerable<string>, IEnumerable<string>> expand = null; 
expand = xs => 
{ 
    if (xs != null && xs.Any()) 
    { 
     var head = xs.First(); 
     if (xs.Skip(1).Any()) 
     { 
      return expand(xs.Skip(1)).SelectMany(tail => new [] 
      { 
       head + tail, 
       head + "-" + tail 
      }); 
     } 
     else 
     { 
      return new [] { head }; 
     } 
    } 
    else 
    { 
     return Enumerable.Empty<string>(); 
    } 
}; 

var keyword = "A-B-C-D"; 

var parts = keyword.Split('-'); 

var results = expand(parts); 

Я получаю:

 
ABCD 
A-BCD 
AB-CD 
A-B-CD 
ABC-D 
A-BC-D 
AB-C-D 
A-B-C-D 

Answer 4

Взгляните на свои примеры. Вы заметили образец?

• С 1 дефисами имеется 2 возможности.
• С двумя дефисами есть 4 возможности.
• С тремя дефисами имеется 8 возможностей.

Количество возможностей: 2 ⁿ.

Это буквально экспоненциальный рост, поэтому, если в строке слишком много дефисов, это быстро станет невозможным для печати всех них. (Всего 30 дефисов насчитывают более миллиарда комбинаций!)

При этом для меньшего количества дефисов может быть интересно создать список. Чтобы сделать это, вы можете думать о каждом дефис как бит в двоичном числе. Если бит равен 1, присутствует дефис, иначе это не так. Таким образом, это предполагает довольно простое решение:

1. Split исходная строка на дефис
2. Пусть п = число дефисов
3. Count от 2 ^н - 1 до 0. Обрабатывать этот счетчик, как битовая маска.
4. Для каждого счета начинайте строить строку, начиная с первой части.
5. Объедините каждую оставшуюся часть строки в порядке, перед которой стоит дефис, только если установлен соответствующий бит в битовой маске.
6. Добавить результирующую строку на выход и продолжить, пока счетчик не будет исчерпан.

Перевод на код, который мы имеем:

public static IEnumerable<string> EnumerateHyphenatedStrings(string s) 
{ 
    string[] parts = s.Split('-'); 
    int n = parts.Length - 1; 
    if (n > 30) throw new Exception("too many hyphens"); 
    for (int m = (1 << n) - 1; m >= 0; m--) 
    { 
     StringBuilder sb = new StringBuilder(parts[0]); 
     for (int i = 1; i <= n; i++) 
     { 
      if ((m & (1 << (i - 1))) > 0) sb.Append('-'); 
      sb.Append(parts[i]); 
     } 
     yield return sb.ToString(); 
    } 
} 

Fiddle: https://dotnetfiddle.net/ne3N8f

Answer 5

Я тестировал этот код и он работает, как указано в вопросе. Я сохранил строки в List<string>.

string str = "AB-C-D-EF-G-HI"; 
string[] splitted = str.Split('-'); 

List<string> finalList = new List<string>(); 

string temp = ""; 

for (int i = 0; i < splitted.Length; i++) 
{ 
    temp += splitted[i]; 
} 
finalList.Add(temp); 
temp = ""; 

for (int diff = 0; diff < splitted.Length-1; diff++) 
{ 
    for (int start = 1, limit = start + diff; limit < splitted.Length; start++, limit++) 
    { 
     int i = 0; 
     while (i < start) 
     { 
      temp += splitted[i++]; 
     } 
     while (i <= limit) 
     { 
      temp += "-"; 
      temp += splitted[i++]; 
     } 
     while (i < splitted.Length) 
     { 
      temp += splitted[i++]; 
     } 
     finalList.Add(temp); 
     temp = ""; 
    } 
}