Эта задача очень интересна всем изучающим математику и проста для понимания. Но проблема возникает, когда программист хочет написать программу для просмотра всех комбинаций строки. вот пример.
String is “abc” and the combinations are: a b c ab ac bc abc
Это простая задача, если мы хотим сделать это вручную. но что, если мы хотим написать для этого общий код. Для этого есть несколько решений.
- С помощью цикла.
- С помощью рекурсии.
1. Использование цикла
Прежде всего, я подробно расскажу, как работает этот алгоритм.
Вам просто нужно начать считать в двоичном формате. 1 в двоичном числе означает, что вы должны показать символ, а 0 в двоичном — скрыть этот символ.
e.g.
в случае строки «abc»
number , binary , string
1 , 001 , c
2 , 010 , b
3 , 011 , bc
4 , 100 , a
5 , 101 , ac
6 , 110 , ab
7 , 111 , abc
Это лучшее решение, которое я когда-либо находил. вы можете сделать это просто с помощью цикла. проблем с памятью не будет.
вот код
#include <iostream> #include <string> #include <math.h> #include<stdio.h> #include <cmath>
using namespace std;
int main() {
string s("abcd"); int condition = pow(2, s.size()); for( int i = 1 ; i < condition ; i++){ int temp = i; for(int j = 0 ; j < s.size() ; j++){ if (temp & 1){//it gives the most right bit of temp cout << s[j]; } temp = temp >> 1;//it shifts temp to the right by 1 bit } cout<<endl; } return 0; }
2. Использование рекурсии
Рекурсия также является хорошим решением, но ее пространственная сложность очень высока, поэтому я бы предпочел цикл для этой проблемы.
#include <iostream>
#include <string>
using namespace std;
void exhaustiveSearch(const string& s, int i, string t = "")
{
if (i == s.size())
cout << t << endl;
else
{
exhaustiveSearch(s, i + 1, t);
exhaustiveSearch(s, i + 1, t + s[i]);
}
}
int main()
{
string s("abc");
exhaustiveSearch(s, 0);
}
Если вам что-то непонятно, не стесняйтесь писать комментарии.
Спасибо.