Отображение наборов и подмножеств строки - PullRequest
Новая
       23

Отображение наборов и подмножеств строки

0 голосов
/ 13 февраля 2020

Я пытаюсь найти подмножества и вывести их в двоичном представлении.

ПРИМЕР: 

000:EMPTY
001:C
010:B
011:B C
100:A
101:A C
110:A B
111:A B C

У меня есть следующий код, который находит все подмножества, но не уверен насчет двоичного? 

#include <iostream>
using namespace std;

void recsub(string sofar, string rest){
  if(rest=="") cout<<sofar<<endl;
  else{
    recsub(sofar+rest[0], rest.substr(1)); //including first letter
    recsub(sofar, rest.substr(1)); //recursion without including first letter.
  }
}

void listsub(string str){
  recsub("",str);
}

int main(){
  listsub("abc");
  return 0;
}

1 Ответ

0 голосов
/ 14 февраля 2020

Вы можете сделать это иначе, сначала сгенерировать mask, а затем сгенерировать соответствующую строку. 

#include <iostream>

using namespace std;

void listsub(const string &str) {
    auto n = str.size();
    // iterate over every binary representation
    for (size_t k = 0; k < (1u << n); ++k) {
        string binary;
        string subset;
        // iterate over every bit from right to left
        for (size_t bit = n ; bit > 0; --bit) {
            bool has_bit = (k & (1 << (bit - 1)));
            binary.push_back(has_bit ? '1' : '0');
            if (has_bit) {
                subset.push_back(str[n - bit]);
            }         
        }
        cout << binary << ':' << subset << endl;
    }
}
int main() {
    listsub("abc");
    return 0;
}
...