C ++ все расположения множества строк - PullRequest
Новая
       18

C ++ все расположения множества строк

1 голос
/ 26 июня 2019

Я пытаюсь сгенерировать все расположения строк в векторе.Например, для 

vector<string> vs = { "a", "b", "c"};

я написал следующий код: 

do{
    for (string s : vs)
        cout << s << " ";
    cout << endl;
} while (std::next_permutation(vs.begin(), vs.end()));

Мой вывод:

abc
acb
bac
bca
cab
cba

но мне не хватает таких комбинаций, как

a
ab
ba
c

и т. д.

Я хотел бы изменить свой код так, чтобы он включал и эти механизмы.Как это сделать?Спасибо!

Ответы [ 2 ]

2 голосов
/ 26 июня 2019

Ваш пример показывает, что вы хотите выводить не только каждое подмножество вашего входа ( Power set ), но и все перестановки каждого набора.

Мне не известен конкретный термин, используемый для этого, но OEIS A000522 называет эти "договоренности".

Чтобы получить то, что вам нужно, вы должны по существу объединить свой код с частичным ответом Джарода (или любой другой реализацией набора мощности, которую вы можете найти здесь): 

void outputAllPermutations(std::vector<std::string> input)
{
    // assert(std::is_sorted(input.begin(), input.end()));
    do
    {
        for (std::string s : input)
            std::cout << s << " ";
        std::cout << std::endl;
    } while (std::next_permutation(input.begin(), input.end()));
}

bool isBitSet(unsigned bitset, std::size_t i)
{
    return (bitset & (1 << i)) != 0;
}

void outputAllArrangements(const std::vector<std::string>& input)
{
    // assert(std::is_sorted(input.begin(), input.end()));
    // assert(input.size() < std::sizeof(unsigned) * 8);

    unsigned bitset = 0;

    std::vector<std::string> subset{};
    subset.reserve(input.size());

    for (unsigned bitset = 0; bitset < (1 << input.size()); ++bitset)
    {
        subset.clear();
        for (std::size_t i = 0; i != input.size(); ++i)
            if (isBitSet(bitset, i))
                subset.push_back(input[i]);

        outputAllPermutations(subset);
    }
}

Демонстрация, включая пример вывода

Я использовал unsigned вместо std::vector<bool>, так как я считаю, что общую логику приращения гораздо проще рассуждать об этом. Теоретически это «ограничивает» код входами, меньшими 32 строк (или 64, в зависимости от платформы), но, учитывая, что длина 22 ввода уже потребует тысяч лет для вывода с 1 циклом ЦП на каждый выход комфортно с этим.

2 голосов
/ 26 июня 2019

Вы можете реализовать Power set с помощью: 

bool increase(std::vector<bool>& bs)
{
    for (std::size_t i = 0; i != bs.size(); ++i) {
        bs[i] = !bs[i];
        if (bs[i] == true) {
            return true;
        }
    }
    return false; // overflow
}

template <typename T>
void PowerSet(const std::vector<T>& v)
{
    std::vector<bool> bitset(v.size());

    do {
        for (std::size_t i = 0; i != v.size(); ++i) {
            if (bitset[i]) {
                std::cout << v[i] << " ";
            }
        }
        std::cout << std::endl;
    } while (increase(bitset));
}

Демо

Затем выполните перестановку каждого набора, что-то вроде: 

bool increase(std::vector<bool>& bs)
{
    for (std::size_t i = 0; i != bs.size(); ++i) {
        bs[i] = !bs[i];
        if (bs[i] == true) {
            return true;
        }
    }
    return false; // overflow
}

template <typename T, typename F>
void PowerSet(const std::vector<T>& v, F f)
{
    std::vector<bool> bitset(v.size());

    do {
        f(v, bitset);
    } while (increase(bitset));
}

template <typename T, typename F>
void AllArrangements(const std::vector<T>& v, F f)
{
    PowerSet(v, [f](const std::vector<T>& v, const std::vector<bool>& bitset){
        std::vector<T> toPermute;
        for (std::size_t i = 0; i != v.size(); ++i) {
            if (bitset[i]) {
                toPermute.push_back(v[i]);
            }
        }
        do {
            f(toPermute);
        } while (std::next_permutation(toPermute.begin(), toPermute.end()));
    });
}

Демо

...