#include <iostream>
#include <vector>
#include <algorithm>
template <typename IT>
bool nextPartialPerm(IT beg, IT mid, IT end) {
if (beg == mid) { return false; }
if (mid == end) { return std::next_permutation(beg, end); }
auto p1 = mid;
while (p1 != end && *(mid - 1) >= *p1)
++p1;
if (p1 != end) {
std::swap(*p1, *(mid - 1));
return true;
} else {
std::reverse(mid, end);
auto p3 = make_reverse_iterator(mid);
while (p3 != make_reverse_iterator(beg) && *(p3 - 1) <= *p3)
++p3;
if (p3 == make_reverse_iterator(beg)) { std::reverse(beg, end); return false;}
auto p2 = end - 1;
while (*p2 <= *p3)
--p2;
std::swap(*p3, *p2);
std::reverse(p3.base() /*+ 1*/, end);
return true;
}
}
int main() {
std::vector<int> z = {1, 1, 2, 3, 4, 4};
int m = 3;
int n = z.size();
do {
for (int j = 0; j < m; ++j)
std::cout << z[j] << ' ';
std::cout << std::endl;
} while (nextPartialPerm(z.begin(), z.begin() + m, z.end()));
for (int j = 0; j < n; ++j)
std::cout << z[j] << ' ';
std::cout << std::endl;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8YWxnb3JpdGhtPgoKdGVtcGxhdGUgPHR5cGVuYW1lIElUPgpib29sIG5leHRQYXJ0aWFsUGVybShJVCBiZWcsIElUIG1pZCwgSVQgZW5kKSB7CiAgICBpZiAoYmVnID09IG1pZCkgeyByZXR1cm4gZmFsc2U7IH0KICAgIGlmIChtaWQgPT0gZW5kKSB7IHJldHVybiBzdGQ6Om5leHRfcGVybXV0YXRpb24oYmVnLCBlbmQpOyB9CgogICAgYXV0byBwMSA9IG1pZDsKICAgIAogICAgd2hpbGUgKHAxICE9IGVuZCAmJiAqKG1pZCAtIDEpID49ICpwMSkKICAgICAgICArK3AxOwogICAgCiAgICBpZiAocDEgIT0gZW5kKSB7CiAgICAgICAgc3RkOjpzd2FwKCpwMSwgKihtaWQgLSAxKSk7CiAgICAgICAgcmV0dXJuIHRydWU7CiAgICB9IGVsc2UgewogICAgICAgIHN0ZDo6cmV2ZXJzZShtaWQsIGVuZCk7CiAgICAgICAgYXV0byBwMyA9IG1ha2VfcmV2ZXJzZV9pdGVyYXRvcihtaWQpOwogICAgICAgIAogICAgICAgIHdoaWxlIChwMyAhPSBtYWtlX3JldmVyc2VfaXRlcmF0b3IoYmVnKSAmJiAqKHAzIC0gMSkgPD0gKnAzKQogICAgICAgICAgICArK3AzOwogICAgICAgIAogICAgICAgIGlmIChwMyA9PSBtYWtlX3JldmVyc2VfaXRlcmF0b3IoYmVnKSkgeyBzdGQ6OnJldmVyc2UoYmVnLCBlbmQpOyAgcmV0dXJuIGZhbHNlO30KICAgICAgICAKICAgICAgICBhdXRvIHAyID0gZW5kIC0gMTsKICAgICAgICAKICAgICAgICB3aGlsZSAoKnAyIDw9ICpwMykKICAgICAgICAgICAgLS1wMjsKICAgICAgICAKICAgICAgICBzdGQ6OnN3YXAoKnAzLCAqcDIpOwogICAgICAgIHN0ZDo6cmV2ZXJzZShwMy5iYXNlKCkgLyorIDEqLywgZW5kKTsKICAgICAgICByZXR1cm4gdHJ1ZTsKICAgIH0KfQoKaW50IG1haW4oKSB7CiAgICBzdGQ6OnZlY3RvcjxpbnQ+IHogPSB7MSwgMSwgMiwgMywgNCwgNH07CiAgICBpbnQgbSA9IDM7CiAgICBpbnQgbiA9IHouc2l6ZSgpOwogICAgCiAgICBkbyB7CiAgICAgICAgZm9yIChpbnQgaiA9IDA7IGogPCBtOyArK2opCiAgICAgICAgICAgIHN0ZDo6Y291dCA8PCB6W2pdIDw8ICcgJzsKICAgICAgICAKICAgICAgICBzdGQ6OmNvdXQgPDwgc3RkOjplbmRsOwogICAgfSB3aGlsZSAobmV4dFBhcnRpYWxQZXJtKHouYmVnaW4oKSwgei5iZWdpbigpICsgbSwgei5lbmQoKSkpOwoKICAgIGZvciAoaW50IGogPSAwOyBqIDwgbjsgKytqKQogICAgICAgIHN0ZDo6Y291dCA8PCB6W2pdIDw8ICcgJzsKICAgIAogICAgc3RkOjpjb3V0IDw8IHN0ZDo6ZW5kbDsKfQo=