Рекурсивно генерировать упорядоченные подстроки из упорядоченной последовательности символов?

Question

Отредактировано после получения ответов

Некоторые отличные ответы здесь. Мне нравится Джош, потому что он такой умный и использует C ++. Однако я решил принять ответ Дейва из-за его простоты и рекурсии. Я проверил их обоих, и они дали одинаковые правильные результаты (хотя и в другом порядке). Итак, еще раз спасибо всем.

---

Скажем, у меня есть строка s символов s [0]: s [N] и где каждый символ s [i] <= s [i + 1] Например строка </p>

aaacdddghzz

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

Так, например, я бы получил

a
aa
aaa
ad
aad
aaad
add
aadd
aaadd
addd
aaddd
aaaddd
d
dd
ddd
.
.
.
ac
aac
.
.
.
acdddghzz
aacdddghzz
aaacdddghzz

Но не

ca
hdz
...etc

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

Для строки aaacdddghzz

a=3
d=3
c=1
g=1
h=1
z=2

и формула (a+1)(c+1)(d+1)(g+1)(h+1)(z+1) = 4*4*2*2*2*3 = 384. Есть 384 подстроки, которые поддерживают отношение s [i] <= s [i + 1]. </p>

Итак, вопрос в том, как мне сгенерировать эти 384 подстроки рекурсивно? На самом деле итеративный метод был бы таким же хорошим, может быть, лучше, так как большие строки с множеством уникальных символов могут вызвать переполнение стека. Это звучит как домашнее задание, но это не так. Я просто бесполезен при разработке таких алгоритмов. Я использую C ++, но псевдокод будет в порядке.

Answer 1

Поправка к ответу Райана Шоу выше:

Вместо того, чтобы считать в двоичном виде, посчитайте каждую цифру в базе в зависимости от количества каждой буквы. Например:

a d c g h z
3 3 1 1 1 2

Итак, посчитайте:

0 0 0 0 0 0
0 0 0 0 0 1
0 0 0 0 0 2
0 0 0 0 1 0
0 0 0 0 1 1 
0 0 0 0 1 2
0 0 0 1 0 0
...
0 0 0 1 1 2
0 0 1 0 0 0
...
0 0 1 1 1 2
0 1 0 0 0 0 
...
0 3 1 1 1 2
1 0 0 0 0 0
...
3 3 1 1 1 2

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

1 2 0 0 1 1 => addhz
3 0 0 0 1 2 => aaahzz

И код:

void GetCounts(const string &source, vector<char> &characters, vector<int> &counts)
{
    characters.clear();
    counts.clear();

    char currentChar = 0;
    for (string::const_iterator iSource = source.begin(); iSource != source.end(); ++iSource)
    {
        if (*iSource == currentChar)
            counts.back()++;
        else
        {
            characters.push_back(*iSource);
            counts.push_back(1);
            currentChar = *iSource;
        }
    }
}

bool Advance(vector<int> &current, const vector<int> &max)
{
    if (current.size() == 0)
        return false;

    current[0]++;
    for (size_t index = 0; index < current.size() - 1 && current[index] > max[index]; ++index)
    {
        current[index] = 0;
        current[index + 1]++;
    }
    if (current.back() > max.back())
        return false;
    return true;
}

string ToString(const vector<int> &current, const vector<char> &characters)
{
    string result;
    for (size_t index = 0; index < characters.size(); ++index)
        for (int i = 0; i < current[index]; ++i)
            result += characters[index];
    return result;
}

int main() { 
    vector<int> max;
    vector<char> characters;

    GetCounts("aaadddcghzz", characters, max);

    vector<int> current(characters.size(), 0);
    int index = 1;
    while (Advance(current, max))
    {
        cout << index++ << ":" << ToString(current, characters) << endl;
    }
}

Answer 2

Ниже приведен рекурсивный алгоритм для генерации всех подпоследовательностей.

/* in C -- I hope it will be intelligible */

#include <stdio.h>

static char input[] = "aaabbbccc";
static char output[sizeof input];

/* i is the current index in the input string
 * j is the current index in the output string
 */
static void printsubs(int i, int j) {
    /* print the current output string */
    output[j] = '\0';
    printf("%s\n", output);
    /* extend the output by each character from each remaining group and call ourselves recursively */
    while(input[i] != '\0') {
        output[j] = input[i];
        printsubs(i + 1, j + 1);
        /* find the next group of characters */
        do ++i;
        while(input[i] == input[i - 1]);
    }
}

int main(void) {
    printsubs(0, 0);
    return 0;
}

Если вы заинтересованы только в подсчете количества подпоследовательностей, вы можете сделать это намного эффективнее. Просто подсчитайте, сколько каждой буквы есть, добавьте 1 к каждому значению и умножьте их вместе. В приведенном выше примере есть 3 a, 3 b, 3 c и 2 d для (3 + 1) * (3 + 1) * (3 + 1) * (2 + 1) = 192 подпоследовательности. Это работает потому, что вы можете выбирать между 0 и 3 a, 0 и 3 b, 0 и 3 c, и 0 и 2 d, и все эти варианты независимы .

Answer 3

На самом деле ваш вопрос - перечислить все подмножества из заданного набора.

Учитывая набор {a, a, a, d, d, d, c, g, h, z, z}, ваша цель - перечислить все его уникальные подмножества в порядке, кроме пустого набора: {А} {А, а} {А, а, а} {А, а, а, д}

Существует быстрый способ составить список всех подмножеств из данного набора.

Давайте возьмем {ABC} в качестве примера:

{}     = 000
{C}    = 001
{B}    = 010
{BC}   = 011
{A}    = 100
{AC}   = 101
{AB}   = 110
{ABC}  = 111

Видите образец? Просто используйте целое число, которое увеличивается от 0 до 2 ^ n - 1. Если i-я цифра целого числа равна 1, извлеките i-й элемент из набора.

Примечание: поскольку в вашем примере в строке есть дубликаты; поэтому после генерации вам может понадобиться удалить дубликаты.

Надеюсь, это поможет вам.

Answer 4

Я использовал этот код Java (http://www.merriampark.com/comb.htm) и получил только 383. Код генерирует слишком много дубликатов, поэтому мне пришлось выбросить их много. В итоге я получил только 383 (см. Ниже) Возможно, вы захотите взглянуть на код c ++ для next-combinatiom в stl (но я нигде не мог легко найти источник). Набор мощности, вероятно, лучший подход (но у вас также могут быть дубликаты). *

a
aa
aaa
aaac
aaacg
aaacgh
aaacghz
aaacghzz
aaacgz
aaacgzz
aaach
aaachz
aaachzz
aaacz
aaaczz
aaad
aaadc
aaadcg
aaadcgh
aaadcghz
aaadcghzz
aaadcgz
aaadcgzz
aaadch
aaadchz
aaadchzz
aaadcz
aaadczz
aaadd
aaaddc
aaaddcg
aaaddcgh
aaaddcghz
aaaddcghzz
aaaddcgz
aaaddcgzz
aaaddch
aaaddchz
aaaddchzz
aaaddcz
aaaddczz
aaaddd
aaadddc
aaadddcg
aaadddcgh
aaadddcghz
aaadddcghzz
aaadddcgz
aaadddcgzz
aaadddch
aaadddchz
aaadddchzz
aaadddcz
aaadddczz
aaadddg
aaadddgh
aaadddghz
aaadddghzz
aaadddgz
aaadddgzz
aaadddh
aaadddhz
aaadddhzz
aaadddz
aaadddzz
aaaddg
aaaddgh
aaaddghz
aaaddghzz
aaaddgz
aaaddgzz
aaaddh
aaaddhz
aaaddhzz
aaaddz
aaaddzz
aaadg
aaadgh
aaadghz
aaadghzz
aaadgz
aaadgzz
aaadh
aaadhz
aaadhzz
aaadz
aaadzz
aaag
aaagh
aaaghz
aaaghzz
aaagz
aaagzz
aaah
aaahz
aaahzz
aaaz
aaazz
aac
aacg
aacgh
aacghz
aacghzz
aacgz
aacgzz
aach
aachz
aachzz
aacz
aaczz
aad
aadc
aadcg
aadcgh
aadcghz
aadcghzz
aadcgz
aadcgzz
aadch
aadchz
aadchzz
aadcz
aadczz
aadd
aaddc
aaddcg
aaddcgh
aaddcghz
aaddcghzz
aaddcgz
aaddcgzz
aaddch
aaddchz
aaddchzz
aaddcz
aaddczz
aaddd
aadddc
aadddcg
aadddcgh
aadddcghz
aadddcghzz
aadddcgz
aadddcgzz
aadddch
aadddchz
aadddchzz
aadddcz
aadddczz
aadddg
aadddgh
aadddghz
aadddghzz
aadddgz
aadddgzz
aadddh
aadddhz
aadddhzz
aadddz
aadddzz
aaddg
aaddgh
aaddghz
aaddghzz
aaddgz
aaddgzz
aaddh
aaddhz
aaddhzz
aaddz
aaddzz
aadg
aadgh
aadghz
aadghzz
aadgz
aadgzz
aadh
aadhz
aadhzz
aadz
aadzz
aag
aagh
aaghz
aaghzz
aagz
aagzz
aah
aahz
aahzz
aaz
aazz
ac
acg
acgh
acghz
acghzz
acgz
acgzz
ach
achz
achzz
acz
aczz
ad
adc
adcg
adcgh
adcghz
adcghzz
adcgz
adcgzz
adch
adchz
adchzz
adcz
adczz
add
addc
addcg
addcgh
addcghz
addcghzz
addcgz
addcgzz
addch
addchz
addchzz
addcz
addczz
addd
adddc
adddcg
adddcgh
adddcghz
adddcghzz
adddcgz
adddcgzz
adddch
adddchz
adddchzz
adddcz
adddczz
adddg
adddgh
adddghz
adddghzz
adddgz
adddgzz
adddh
adddhz
adddhzz
adddz
adddzz
addg
addgh
addghz
addghzz
addgz
addgzz
addh
addhz
addhzz
addz
addzz
adg
adgh
adghz
adghzz
adgz
adgzz
adh
adhz
adhzz
adz
adzz
ag
agh
aghz
aghzz
agz
agzz
ah
ahz
ahzz
az
azz
c
cg
cgh
cghz
cghzz
cgz
cgzz
ch
chz
chzz
cz
czz
d
dc
dcg
dcgh
dcghz
dcghzz
dcgz
dcgzz
dch
dchz
dchzz
dcz
dczz
dd
ddc
ddcg
ddcgh
ddcghz
ddcghzz
ddcgz
ddcgzz
ddch
ddchz
ddchzz
ddcz
ddczz
ddd
dddc
dddcg
dddcgh
dddcghz
dddcghzz
dddcgz
dddcgzz
dddch
dddchz
dddchzz
dddcz
dddczz
dddg
dddgh
dddghz
dddghzz
dddgz
dddgzz
dddh
dddhz
dddhzz
dddz
dddzz
ddg
ddgh
ddghz
ddghzz
ddgz
ddgzz
ddh
ddhz
ddhzz
ddz
ddzz
dg
dgh
dghz
dghzz
dgz
dgzz
dh
dhz
dhzz
dz
dzz
g
gh
ghz
ghzz
gz
gzz
h
hz
hzz
z
zz

Answer 5

Что ж, мне кажется, что одно решение, которое похоже на ваше, но не соответствует вашему выводу (см. Мои комментарии по этому вопросу), - это просто перебирать список хвостов исходной строки ( например, для «abc» итерируйте «abc», «bc» и «c»), и для каждого из них создайте список префиксов («abc», «ab», «a», затем «bc», «б», затем «в»). Как это сравнить с тем, что вы хотите?