문자열 조합 만들기(string combination)

팀장님이 개인적으로 필요하다며, 만들어 줄 수 있냐고 하셔서 급하게 만들어본 코드.

string instance를 substr을 통해 계속 생성해 사용하도록 되어있어, 개선의 여지가 있을 것 같다.

하지만, 이런 소소한 문제 해결에 행복감을 느끼게 되다니, 개인적으로도 내 자신이 안타깝다... oTL

다른 사람이 리뷰 좀 해 주면 좋겠다.

(Aug. 10 2016) 시간 복잡도 분석을 해 봤는데, M^(N-1)이 된다.

만약 10진수(M=10)에 대해, N = 1인 경우 1ms가 걸린다고 하면, N = 4 인경우 1초에 불과하지만, N = 9에 대한 모든 경우의 수를 만들려면 꼬박 하루가 지나고도 3시간 정도가 더 필요하며, N = 10인 경우에는 대략 11일이 걸린다. (만약 결과를 얻기 전에 stack overflow가 발생하지 않는다면 말이다...) -_-;

무시 무시한 구현인데, 모든 조합을 만들어 내려면 이것밖에 없는거 아닌가?@.@

N - 입력 문자열 가운데 x의 개수

      ex) 010-7x0x-00xx의 경우 N = 4

M - 조합에 사용할 문자 집합의 크기(개수)

      ex) 10진수 인 경우 M = 10, 알파벳 대문자의 경우 M = 26

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52

#include <iostream> #include <fstream> #include <string> #include <algorithm> #include <cctype>   void bar(std::string& front, std::string& end, std::ostream& out) {     if (end.empty()) {         out << front << std::endl;         return;     }       auto pos = end.find('x');     if (pos == std::string::npos) {         bar(front + end, std::string(), out);     }     else {         for (int i = 0; i < 10; ++i) {             bar(front + end.substr(0, pos).replace(pos, 1, std::to_string(i)),                 end.substr(pos + 1, end.length()), out);         }     } }   void foo(std::string& input, std::ostream& out = std::cout) {     std::for_each(input.begin(), input.end(), [](char& c) { c = std::tolower(c); });       auto pos = input.find('x');     if (pos == std::string::npos) {         out << input << std::endl;         return;     }       for (int i = 0; i < 10; ++i) {         bar(input.substr(0, pos).replace(pos, 1, std::to_string(i)),             input.substr(pos + 1, input.length()), out);     } }   int main(int argc, char** argv) {     if (argc != 2) {         std::cerr << argv[0] << " 010-7x0x-00xx" << std::endl;         return 0;     }       foo(std::string(argv[1]), std::ofstream("list.txt"));       return 0; }