Как использовать стек для растягивания строки ввода k раз

Question

Растяжение входной строки генерируется путем повторения каждого символа в порядке до k раз (и не менее одного раза). Для входной строки «abc» и k = 2 список вывода должен иметь: ab c, aab c, abb c, ab cc, aabb c, aab cc, abb cc, aabb cc.

Я так долго пытался понять это, я не могу получить логику c. Это то, что я до сих пор. Это очень грубая попытка, поскольку я только пытаюсь повторить каждый символ до 2 раз, чтобы попытаться заставить что-то работать: /.

class Ana
{
    public:
        string in_str;
        int len;
        int counter;
}; 

List stretch(string input, int k) {
List final_output; // generate empty list
    stack<class Ana> recurStack; // empty stack that performs the recursion
    Ana init, stacktop, orig; // create a pair to push, to start the stack
    orig.in_str = input; // put the initial string
    orig.len = 0; // this is the fixed string, initially empty
    init.in_str = input; // put the initial string
    init.counter = 0;
    init.len = -1; 
    recurStack.push(init); // push this pair onto the top

    while(!recurStack.empty()) // while the stack is non-empty
    {    
        stacktop = recurStack.top();// get the top pair in stack 
        recurStack.pop(); // remove the top element of stack
        if (stacktop.counter == (input.length() - 1)) 
        {
            final_output.insert(stacktop.in_str); // insert the fixed string onto list
            continue; // pop the next element of stack
        }
        char to_ignore;
        if(stacktop.counter == 1) {
                to_ignore = orig.in_str[stacktop.len];
        }



        for(int i = 0; i < stacktop.in_str.length(); i++) {
            if(to_ignore == stacktop.in_str[i])
                continue;
            char to_insert = stacktop.in_str[i];
            Ana temp;
            temp.in_str = stacktop.in_str;
            temp.len = stacktop.len;
            temp.counter = stacktop.counter;
            temp.in_str.insert(i, 1, to_insert);
            (temp.len) = i;
            (temp.counter)++;
            recurStack.push(temp);
        }       
    }
    return final_output;
}

Answer 1

Может быть, я не до конца понимаю вопрос. В любом случае, я покажу вам очень простое решение, но без использования стека. Если у вас есть требования использовать стек, рекурсивные вызовы или что-то еще, пожалуйста, прокомментируйте, и я разработаю новый ответ.

Но давайте сначала посмотрим на алгоритм. Что вам нужно, это какая-то «комбинация подмножеств» всех букв. Правильный подход заключается в использовании так называемого Power Set и для расчета всех необходимых подмножеств. Это очень просто, используя двоичное представление общего количества подмножеств. Для всех подмножеств набора мощности, в которых установлен бит, мы растянем соответствующую букву.

Растянуть в этом контексте означает просто повторить это k раз.

Предостережение , Поскольку мы используем unsigned long long в качестве идентификатора блока питания, мы можем обрабатывать строки с максимальной длиной 64. Но поверьте мне. Это приведет к тому, что множество подмножеств будет недоступно для вашего компьютера.

Итак, полученный код довольно прост, но требует 3 вложенных цикла.

Пожалуйста, см .:

#include <iostream>
#include <string>
#include <list>
#include <vector>
#include <algorithm>
#include <iterator>

// Make typing easier
using ULL = unsigned long long;

std::list<std::string> stretch(std::string input, size_t k)
{
    // Resulting list. Initialize with given string
    std::list<std::string> result{ input };

    // Go through all requested depths
    for (size_t depth = 0U; depth < k-1; ++depth) {

        // Go through all possible power-set sub-sets for selecting 1 or more letters
        for (ULL subSetID = 1ULL ; subSetID < (1ULL << static_cast<ULL>(input.size())); ++subSetID) {

            // Bit mask, for checking, if a bit in the sub-set is set
            ULL bitMask{ 1ULL };

            // In here, we build the string from a letter or stretched letter
            std::string temp{};

            // Go through all letters of the input string
            for (const char letter : input) {

                // Check, if the bit mask for this powerset element is set, then stretch, else. take letter as is
                temp += std::string(1, letter) + (((subSetID & bitMask) == bitMask) ? std::string(depth + 1, letter) : "");

                // Check next bit
                bitMask <<= 1;
            }
            // Store the new found string in the resulting list
            result.push_back(temp);     
        }
    }
    return result;
}

int main() {
    // Test for string abc with depth 2
    std::list<std::string> l{ stretch("abc",2) };

    // Show result on screen
    std::copy(l.begin(), l.end(), std::ostream_iterator<std::string>(std::cout, "\n"));

    return 0;
}