Элегантный способ создания составных перестановок в C ++ - PullRequest
Новая
       5

Элегантный способ создания составных перестановок в C ++

0 голосов
/ 22 октября 2018

У меня есть класс Test, который содержит два вектора класса Letter, определенного пользователем типа, для которого был реализован оператор меньше чем (<).Как лучше всего сгенерировать все возможные перестановки Test? </p> 

class Test
{
  vector<Letter> letter_box_a;
  vector<Letter> letter_box_b;
}

Так что, если letter_box_a содержит буквы A и B, а letter_box_b содержит C и D, действительными перестановками Test будут (AB) (CD), (BA) (CD), (AB) (DC) и (BA) (DC).

Несмотря на то, что я могу переборщить, я пытался написать лучшую (более элегантную / эффективную) функцию, котораявнутренне вызвал бы std :: next_permutation для нижележащих контейнеров, что позволило бы мне сделать 

Test test;
while (test.set_next_permutation())
{
    // Do the stuff
}

, но это оказалось немного сложнее, чем я ожидал.Мне не обязательно нужно решение STL, но я бы хотел элегантное решение.

Ответы [ 2 ]

0 голосов
/ 22 октября 2018

Я думаю, вы могли бы сделать что-то вроде 

bool Test::set_next_permutation() {
    auto &a = letter_box_a, &b = letter_box_b;  // entirely to shorten the next line
    return std::next_permutation(a.start(), a.end()) || std::next_permutation(b.start(), b.end());
}

(Конечно, цикл while пропустит начальную перестановку в любом случае. Вы хотите do ... whileцикл вместо.)

0 голосов
/ 22 октября 2018

Если вы хотите использовать std::next_permutation, вам нужен вложенный цикл для каждого переставляемого вектора: 

std::string s0 = "ab";
std::string s1 = "cd";

do
{
    do
    {
        cout << s0 << "" << s1 << endl;
    } while (std::next_permutation(s0.begin(), s0.end()));
} while (std::next_permutation(s1.begin(), s1.end()));

Вывод: 

abcd
bacd
abdc
badc

И в классе:

class Foo
{
public:
    Foo(std::string_view arg_a, std::string_view arg_b)
        : a(arg_a)
        , b(arg_b)
        , last(false)
    { }

    void reset_permutations()
    {
        last = false;
    }

    bool next_permutation(std::string& r)
    {
        if (last)
            return false;

        if (not std::next_permutation(a.begin(), a.end()))
            if (not std::next_permutation(b.begin(), b.end()))
                last = true;

        r = a + b;
        return true;
    }

private:
    std::string a, b;
    bool last;
};

int main(int argc, const char *argv[])
{
    Foo foo("ab", "cd");
    string s;
    while (foo.next_permutation(s))
        cout << s << endl;
    return 0;
}
...