Все двоичные строки длины n, содержащие ровно k единиц

Question

По данным числам N и K выведите все строки из нулей и единиц длины N, содержащие ровно K единиц, в лексикографическом порядке.

Входные данные Заданы 2 числа: N и K (0 ≤ K ≤ N, 0 ≤ N ≤ 100)

Выходные данные Необходимо вывести все строки из нулей и единиц длины N, содержащие ровно K единиц, в лексикографическом порядке. Гарантируется, что размер ответа не превышает 10MiB

Примеры

входные данные

4 2

выходные данные

0011

0101

0110

1001

1010

1100

#include <iostream>
#include <vector>
using namespace std;


void gen(int i, int n, int k, vector<int>&res, int count) {
    if (i > n) {
        if (count == k) {
            for (auto el : res) {
                cout << el;
            }
            cout << '\n';
        }
    }
    else {
        for (int j = 0; j < 2; ++j) {
            res[i - 1] = j;
            if (j == 1) {
                count += 1;
                gen(i + 1, n, k, res, count);
                count -= 1;
            }
            else {
                gen(i + 1, n, k, res, count);
            }
        }
    }
}


int main() {
    int n, k, count = 0;
    cin >> n >> k;
    vector <int> res(n);
    gen(1, n, k, res, count);

    return 0;
}

6 тестов не проходят по времени, подскажите, пожалуйста, идеи решения задачи

Answer 1

А воспользоваться стандартным алгоритмом не хотите?

#include <algorithm>
#include <iostream>
#include <string>

using namespace std;

int main(int argc, char* argv[])
{
    int k, n;
    cin >> n >> k;
    string s(n-k,'0');
    s += string(k,'1');
    do
    {
        cout << s << endl;
    } while(next_permutation(s.begin(),s.end()));
}

Задачка отсюда?

Answer 2

Алгоритм

Ваш код перебирает все возможные комбинации из n нулей и единиц. Те комбинации в которых k единиц печатаются. Остальные отбрасываются. Всего комбинаций 2ⁿ. Нужных комбинаций C_n^k = n! / (k!·(n - k)!). Если k близко к нулю или n, второе выражение гораздо меньше первого.

Вашу программу можно доработать так чтобы gen не занималась бесполезным перебором. Заметим что n - i + 1 - число свободных мест, k - count - число единиц, которые надо вписать в комбинацию. Если мест не хватает, продолжать поиск бесполезно. Также бесполезно искать если число единиц которые уже вписаны (count) больше ожидаемого числа единиц в комбинации (k).

В начало функции gen вставьте проверку:

    if (n - i + 1 < k - count || k < count) {
        return;
    }

Без проверки одна секунда:

$ time echo 26 4 | ./a.out | wc
  14950   14950  403650

real  0m0.997s
user  0m1.000s
sys   0m0.000s

С проверкой в сорок раз быстрее:

$ time echo 26 4 | ./a.out | wc
  14950   14950  403650

real  0m0.024s
user  0m0.024s
sys   0m0.004s

Вариант с проверкой на моём железе укладывается в одну секунду если объём вывода меньше 10Mb (условие из задачи). Но запас не так велик.

Печать

Текущее решение печатает ответ посимвольно. Если в ответе 10 миллионов символов, будет сделано 10 миллионов вызовов cout << . А вывод в C++ замечателен своей неэффективностью.

Тип вектора res заменим с int на char. Будем вписывать туда цифры '0' и '1'. В конец добавим перевод строки и нулевой символ. Такой массив можно печатать в один вызов cout << res.data(). Модификация ускоряет программу примерно в четыре раза:

#include <iostream>
#include <vector>
using namespace std;


void gen(int i, int n, int k, vector<char>&res, int count) {
    if (n - i + 1 < k - count || k < count) {
        return;
    }
    if (i > n) {
        if (count == k) {
            cout << res.data();
        }
    }
    else {
        for (int j = 0; j < 2; ++j) {
            res[i - 1] = static_cast<char>('0' + j);
            if (j == 1) {
                count += 1;
                gen(i + 1, n, k, res, count);
                count -= 1;
            }
            else {
                gen(i + 1, n, k, res, count);
            }
        }
    }
}

int main() {
    int n, k, count = 0;
    cin >> n >> k;
    vector <char> res(n + 2);
    res[n] = '\n';
    res[n + 1] = '\0';
    gen(1, n, k, res, count);

    return 0;
}

Программу можно ещё немного подсушить. Это почти не скажется на скорости, но кода будет меньше:

#include <iostream>
#include <vector>
using namespace std;

void gen(int i, int n, char *res, int count) {
    if (i == n) {
        puts(res);
    }
    else {
        if (count < n - i) {
            res[i] = '0';
            gen(i + 1, n, res, count);
        }
        if (0 < count) {
            res[i] = '1';
            gen(i + 1, n, res, count - 1);
        }
    }
}

int main() {
    int n, k;
    cin >> n >> k;
    vector<char> res(n + 1);
    res[n] = '\0';
    gen(0, n, res.data(), k);
}

БЛОГ НА HUSL

Все двоичные строки длины n, содержащие ровно k единиц

Ответы (2 шт):

Алгоритм

Печать