April 28th, 2009

Сочетания и битхак

Задумал написать перебор сочетаний, представляя результат в виде битовой маски. Хотелось сделать совсем без циклов, но один все-таки понадобился. Итак, будем сочетания перебирать в лексикографическом порядке. Только для удобства первая выборка будет представляться в виде 111...111000...000, что соответсвует подмножеству { 1, 2, 3, ..., k }, следующая 111...110100...000 => { 1, 2, ..., k-1, k+1 }, последняя 000...000111...111, соответственно, { n-k+1, n-k+2, ..., n }. Для получения следующего сочетания рассмотрим два случая:
  • Самый младший бит 0. Тогда ясно, что последний элемент в текущей выборке можно увеличить на 1, то есть самый младший установленный бит нужно сместить на одну позицию вправо. Сделать это можно так: n = n ^ (n & -n) | (n & -n) >> 1. Из жж товарища sharpc можно узнать, что кодом n & -n получается число с самым младшим установленным битом. Xor с исходным его снимает, а следующий Or устанавливает его на одну позицию правее.
  • Младший бит 1. В этом случае возможна ситуация, что справа какое-то число r единичных битов (если r == k, то это последнее возможное сочетание). Слева до r имеется число, которое полностью соответсвует первому случаю, то есть имеет вид 11..1100... С ним делается тоже самое, а вот r млаших битов нужно сместить на максимально возможное количество положений влево, пока они не перекрывают хоть один бит в нашем числе. Вот эта часть для меня стала самой трудной и для которой я так и не придумал закрытой формулы :) Решение у меня вышло такое. Сначала получаем число, состоящее только из самых младших r единичных битов, формула имеет вид p = ((n + 1) & -(n + 1)) - 1 и основана на уже упоминавшемся фокусе. Далее ясно, что если его вычесть из исходного числа, то задача сводится к первому пункту. И наконец нам нужно число p сдвинуть влево настолько, насколько это возможно без пересечения, а потом сложить с ответом.
bool next_comb(int& mask, int k) {
if(mask == (1 << k) - 1) return false;
if(!(mask & 1))
mask = mask ^ (mask & -mask) | (mask & -mask) >> 1;
else {
unsigned int u = mask + 1;
unsigned int n = (u & -u) - 1;
u -= n + 1;
u = u ^ (u & -u) | (u & -u) >> 1;
while(!(u & n << 1)) n <<= 1;
mask = u | n;
}
return true;
}

Принимаются предложения по оптимизации :)
  • Current Music
    Annasophia Robb - [Bridge To Terabithia #01] Keep Your Mind Wide Open