Саша Ситников (shuffle_c) wrote,
Саша Ситников
shuffle_c

  • Music:

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

Задумал написать перебор сочетаний, представляя результат в виде битовой маски. Хотелось сделать совсем без циклов, но один все-таки понадобился. Итак, будем сочетания перебирать в лексикографическом порядке. Только для удобства первая выборка будет представляться в виде 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;
}

Принимаются предложения по оптимизации :)
Subscribe

  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 6 comments