Рекурсия против битовой маски для получения всех комбинаций векторных элементов
Практикуя на соревнованиях по программированию (например, ACM, Code Jam и т. Д.), Я столкнулся с некоторыми проблемами, которые требуют от меня создания всех возможных комбинаций некоторых векторных элементов.
Допустим, у меня есть вектор {1,2,3}, мне нужно сгенерировать следующие комбинации (порядок не важен):
1
2
3
1 2
1 3
2 3
1 2 3
Пока что я сделал это с помощью следующего кода:
void getCombinations(int a)
{
printCombination();
for(int j=a;j<vec.size();j++)
{
combination.pb(vec.at(j));
getCombinations(j+1);
combination.pop_back();
}
}
Вызов getCombination (0); делает работу за меня Но есть ли лучший (более быстрый) способ? Я недавно слышал о битовой маскировке. Как я понял, это просто для всех чисел от 1 до 2 ^ N-1, я превращаю это число в двоичный файл, где 1 и 0 будут представлять, включен ли этот элемент в комбинации.
Как я могу реализовать это эффективно, хотя? Если я перевожу каждое число в двоичную форму стандартным способом (путем деления на 2 все время), а затем проверяю все цифры, это, похоже, тратит много времени. Есть ли более быстрый способ? Должен ли я продолжать использовать рекурсию (если я не столкнусь с некоторыми большими числами, когда рекурсия не может выполнить работу (ограничение стека))?
Решение
Количество комбинаций, которые вы можете получить, равно 2 ^ n, где n — количество ваших элементов. Вы можете интерпретировать каждое целое число от 0 до 2 ^ n -1 как маску. В вашем примере (элементы 1, 2, 3) у вас есть 3 элемента, и поэтому маски будут 000, 001, 010, 011, 100, 101, 110 и 111. Пусть каждое место в маске представляет один из ваших элементов. Для места, которое имеет 1, возьмите соответствующий элемент, иначе, если место содержит 0, оставьте элемент вне. Например, число 5 будет маской 101, и она сгенерирует эту комбинацию: 1, 3.
Если вы хотите иметь быстрый и относительно короткий код, вы можете сделать это так:
#include <cstdio>
#include <vector>
using namespace std;
int main(){
vector<int> elements;
elements.push_back(1);
elements.push_back(2);
elements.push_back(3);
// 1<<n is essentially pow(2, n), but much faster and only for integers
// the iterator i will be our mask i.e. its binary form will tell us which elements to use and which not
for (int i=0;i<(1<<elements.size());++i){
printf("Combination #%d:", i+1);
for (int j=0;j<elements.size();++j){
// 1<<j shifts the 1 for j places and then we check j-th binary digit of i
if (i&(1<<j)){
printf(" %d", elements[j]);
}
}
printf("\n");
}
return 0;
}
Другие решения
detector