Что-то я не понял, что все-таки нужно - найти распределение или отсортировать? Это очень разные вещи. Чтобы найти распределение перебор необязателен. А в сортировке - от перебора никуда не денешься.

MasterZivЭто из "Алгоритмические трюки для программистов" Похоже это очень старый и известный трюк. Вот что про него пишет Кнут в mmix-arith.w :

Here's a fun way to count the number of bits in a tetrabyte.
[This classical trick is called the ``Gillies--Miller method
for sideways addition'' in {\sl The Preparation of Programs
for an Electronic Digital Computer\/} by Wilkes, Wheeler, and
Gill, second edition (Reading, Mass.:\ Addison--Wesley, 1957),
191--193. Some of the tricks used here were suggested by
Balbir Singh, Peter Rossmanith, and Stefan Schwoon.]

+2 wrote:
> Автор: +2
> +2
> в последовательности подобной A047869
> <http://www.research.att.com/~njas/sequences/A047869>, но для 32-битного
> целого найти значение.
>
>
> Точнее, не именно в такой, а начинающейся с конкретного значения
> (например, 35) и завершающейся конкретным значением (например, 81).

То есть "набор чисел отсортировать сначала по количеству единиц
двоичного представления, внутри каждой группы - в порядке возрастания,
после чего выбрать всего одно - по его порядковому номеру в получившемся
массиве."

Мысль, возможно, не очень внятная, но ковыряться не хочется, а, по
ощущениям - похоже на то, что вы ищите. Я про алгоритмический поиск, а
не грубой силой - поиск по заданному количеству бит и порядковому номеру
числа.

Под распределением здесь я понимаю нечто близкое к понятию из теории
вероятности - количество чисел в интервале, имеющих 1, 2, ... n бит в
двоичном представлении. Можно представить его как массив счётчиков,
размеренностью от 0 до количества бит в слове.
Над распределением можно объявить операции сложения и вычитания -
складывая и вычитая соответствующие элементы двух распределений.

Дальше можно заметить три интересных свойства:
1) Рекуррентность полуинтервала. Возьмём n чисел, где n - степень
двойки. Разделим на две части - 0..n/2-1 и n/2..n. Пусть нам известно
распределение для первой половины. Тогда, для второй половины (там, где
добавляется старший бит) его можно вычислить, увеличив все элементы
распределения вплоть до позиции делящего бита первой половины на единицу.

2) Пусть дан интервал от m до n. Тогда можно рассчитать распределение
для интервала разделив его на две части - как сумму или разность
распределений двух не пересекающихся интервалов - например, от
(m..0)+(1..n), или (0..n)-(1..m). в зависимости от положения интервалов
относительно нуля.

3) Упорядоченность искомого числа относительно последовательного
просмотра интервалов. Проматривая интервалы последовательно, начиная с
распределения -(0..m) [это знак минус], и находя их распределения мы
можем отслеживать лежит ли искомое порядковое значение в рассматриваемом
интервале.

Свойства (1) и (2) позволяют рассчитать распределение для любого числа.
По ощущениям, требуемое время порядка - 1/2 O(n^2), где n - число бит в
представлении максимального числа. Подход еще не оптимален, но должно
быть гораздо быстрее перебора.
Posted via ActualForum NNTP Server 1.4

teras wrote:
> Дальше можно заметить три интересных свойства:
> 1) Рекуррентность полуинтервала. Возьмём n чисел, где n - степень
> двойки. Разделим на две части - 0..n/2-1 и n/2..n. Пусть нам известно

ммм. Второй - до n-1, конечно. На второй взгляд, больше косяков не
нашел. :-)
Posted via ActualForum NNTP Server 1.4

+2 wrote:
> Автор: +2
> Я тут уже в теорию наборов углубился.. или как правильно перевести set
> theory? По-моему очень похожая проблема.

Теория множеств.
Posted via ActualForum NNTP Server 1.4

+2 wrote:
>
> Вот я что еще тут заметил:
>
> 1. для n == 2^x в нулевом подмножестве находится одна запись (0), в
> первом - n записей, во втором - (n-1)*n/2 записей, в третьем пока думаю :)
> 2. для каждого (unsigned) подмножества x минимальное значение в этом
> подмножестве равно 2^x - 1
> 3. для каждого (unsigned) подмножества x максимальное значение в этом
> подмножестве равно 2^n - 2^(n-x)

А все-таки, если не трудно - что вы думаете о том, что я написал? Не
было времени, не оптимально, не подходит, не работает, не понятно?
Похоже, время я неправильно оценил - оно будет меньше. Пропорционально
количеству бит.
Posted via ActualForum NNTP Server 1.4