Перебір усих можливих комбінацій bool

Задача

Для N змінних типу bool треба знайти всі варіанти комбінацій їх значень.

Рішення

Ідея полягає в тому що після того як змінено значення однієї змінної в true (починаємо з останньої) встановлюємо усі що йдуть за нею в false. Кожна наступна ітерація починає з останнього зміненого значення.

   1:      bool* vals = new bool[N];
   2:      for (int i = 0; i < N; ++i) vals[i] = false;
   3:   
   4:      bool cont = true;
   5:      while (cont)
   6:      {
   7:          for (int j = 0; j < N; ++j) 
   8:          {
   9:              cout << (vals[j] ? "t" : "f") << ", ";
  10:          }
  11:          cout << 'b' << endl;
  12:   
  13:          cont  = false;
  14:   
  15:          for (int i = N - 1; i >=0; --i)
  16:          {
  17:              if (!vals[i])
  18:              {
  19:                  vals[i] = true;
  20:                  cont = true;
  21:   
  22:                  for (++i; i < N; ++i) vals[i] = false;
  23:   
  24:                  break;
  25:              }
  26:          }
  27:      }
  28:   
  29:      delete [] vals;

 

Оптимізація

Абсолютно зайвим є витрачання цілого байта на значення яке може буте збереженим в одному біті. Тож можна об’єднати 8, або навіть більше значень в одному.

   1:  template <class T>
   2:  unsigned getBit(size_t index, T* storage, size_t size)
   3:  {
   4:      auto position = index / (sizeof(T) * CHAR_BIT);
   5:      auto bit = index % (sizeof(T) * CHAR_BIT);
   6:      
   7:      return (storage[size - position - 1] >> bit) & 1;
   8:  }
   9:   
  10:  typedef unsigned char storageType;
  11:  const int bitsInPosition = sizeof(storageType) * CHAR_BIT;
  12:   
  13:  ...
  14:      auto positions = N / bitsInPosition;
  15:      if (N % bitsInPosition > 0) ++positions;
  16:      storageType* vals = new storageType[positions];
  17:      auto mask0Position = (1 << (N % bitsInPosition)) - 1;
  18:   
  19:      for (auto i = 0; i < positions; ++i) vals[i] = 0;
  20:   
  21:      for (size_t i = positions - 1; ;)
  22:      {
  23:          for (size_t j = 0; j < N; ++j) 
  24:          {
  25:              cout << getBit(j, vals, positions);
  26:          }
  27:          cout << endl;
  28:   
  29:          if ((++vals[i] == 0) ||
  30:              (i == 0 && ((vals[0] & mask0Position) == 0)))
  31:          {
  32:              if (i == 0)
  33:              {
  34:                  break;
  35:              }
  36:              
  37:              while (++vals[--i] == 0);
  38:              i = positions - 1;
  39:          }
  40:      }
  41:   
  42:      delete [] vals;
  43:  

 

Залишити відповідь

Зайти з допомогою: