Задача
Для 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: