строка разбивается на все возможные комбинации - PullRequest
Новая
       5

строка разбивается на все возможные комбинации

0 голосов
/ 03 марта 2020

для данной строки "AB C", i wi sh, чтобы получить все возможные комбинации символов из нее по возрастанию и без пропуска символа, результат должен быть: ["A", "B", "C"], ["AB", "C"], ["AB C"], ["A", "B C"]

Любая идея, как можно я достигну этого? Я думал использовать вложенный для l oop, чтобы получить все компоненты: 

string input="ABCD";
List<string> component=new List<string>();

for(int i=0;i<=input.Length;i++){
    for(int j=1;j<=(input.Length-i);j++){
        component.Add(input.Substring(i,j));
    }
}

Но я понятия не имею, как поместить их в группу, как показано выше. Любой совет приветствуется.

1 Ответ

0 голосов
/ 03 марта 2020

Вы можете go об этом несколькими способами.

Одним из способов является рекурсия . Сохраняйте текущий список подстрок и общий список результатов. На верхнем уровне переберите все возможные пробелы. Разбейте строку на подстроку и все остальное. Это должно включать в себя "пробел" в конце, где вы разбиваете строку на себя и пустую строку как остальные. Добавьте (непустую) подстроку к текущему списку и выполните возврат к остальной части строки. Когда остальная часть строки пуста, добавьте текущий список в общий список результатов. Это даст вам все 2ⁿ возможностей для строки с n + 1 буквой.

Псевдокод: 

// recursive function
function splits_r(str, current, res)
{
    if (str.length == 0) {
        res += [current]
    } else {
        for (i = 0;  i < str.length; i++) {
            splits_r(str.substr(i + 1, end),
                current + [str.substr(0, i + 1)], res)
        }
    }
}

// wrapper to get the recursion going                
function splits(str)
{
    res = [];

    splits_r(str, [], res);

    return res;
}

Другим способом является перечисление из все возможности. Есть две возможности для строки с n + 1 буквой. Вы можете рассматривать одну отдельную возможность как комбинацию расщеплений и неразделений. Например: 

enum        splits              result                  

0 0 0       A   B   C   D       "ABCD"                  
0 0 1       A   B   C | D       "ABC", "D"              
0 1 0       A   B | C   D       "AB", "CD"              
0 1 1       A   B | C | D       "AB", "C", "D"          
1 0 0       A | B   C   D       "A", "BCD"              
1 0 1       A | B   C | D       "A", "BC", "D"          
1 1 0       A | B | C   D       "A", "B", "CD"          
1 1 1       A | B | C | D       "A", "B", "C", "D"

В перечислении используется 0 для разделения и 1 для разделения. Это можно рассматривать как двоичное число. Если вы знакомы с побитовыми операциями , теперь вы можете перечислить все значения от 0 до 2ⁿ и выяснить, где находятся разбиения.

Псевдокод: 

function splits(str)
{
    let m = str.length - 1;     // possible gap positions
    let n = (1 << m);           // == pow(2, m)
    let res = []

    for (i = 0; i < n; i++) { 
        let last = 0
        let current = []

        for (j = 0; j < m; j++) {   // loop over all gaps
            if (i & (1 << j)) {     // test for split
                current.append(str.substr(last, j + 1));
                last = j + 1;
            }
        }

        current.append(s[last:])        
        res.append(current);

    return res;
}
...