- 01
- 02
- 03
- 04
- 05
- 06
- 07
- 08
- 09
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
#ifndef SOCHET_H
#define SOCHET_H
// Сдвигает самую младшую единицу в сторону младшего разряда
#define shiftLast1Right(x) ( (x-1)^((x^(x-1)) >> 2) )
// Дописывает 1 после самой младшей единицы
#define add1AfterLast1(x) ( x | ((x^(x-1))+1) >> 2 )
template<class T>
class Sochet
{
public:
T value;
//////////////////////////////////////////////////////////////////////////
Sochet():value(0) { }
Sochet(int n, int k) {
firstTurn(n, k);
}
~Sochet() {
value = 0;
}
//////////////////////////////////////////////////////////////////////////
// Первая комбинация
// В первоначальной ситуации все К единиц располагаются в старших битах
void firstTurn(int n, int k) {
value = ( ( T(1) << k ) - 1 ) << (n - k);
}
// Нахождение следующей комбинации
// Возвращает false в случае последней комбинации
bool nextTurn()
{
// Отлов последней комбинации
if (value & (value+1) == 0)
return false;
// Условие по младшему биту: 1 или 0
if (value & 1)
{
value >>= 1;
nextTurn();
value = add1AfterLast1(value << 1);
} else
value = shiftLast1Right(value);
return true;
}
}
#endif // SOCHET_H
Шаблон перебора всех сочетаний/выборок в много разрядных числах.
Пример перебираемых чисел для N=5, K=3:
11100
11010
11001
10110
10101
10011
01110
01101
01011
00111
// Код выглядит сочно(особенно дефайны), зато всё работает максимально быстро.
// Статья про этот алгоритм: http://k06a.blogspot.com/2009/04/blog-post_08.html
Follow us!
Если бы я запостил одни дефайны - было бы не понят нахрена они вообще такие нужны.
Комментарии для кого писали, батенька?