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

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

+2 wrote:
> Автор: +2
> +2
> __Rosty__
> Например первое число из 3х единиц равно 7, второе 13, третье 14.
>
>
> Я согласен. С ходу, назовёте 300-е число из 3 единиц?
>

Насколько я понимаю, тут речь идет о том, что если рассматривать числа
подряд, их не нужно сортировать. То, что я назвал упорядоченностью.

Про остальное, если мысль была примерно такая. Нарисую таблицу для
наглядности:

00000 01000 10000 11000
00001 01001 10001 11001
00010 01010 10010 11010
00011 01011 10011 11011
00100 01100 10100 11100
00101 01101 10101 11101
00110 01110 10110 11110
00111 01111 10111 11111

Каждое число можно представить в виде суммы степеней двойки (что
соответствует его представлению в обычных компьютерах). Например, 29 =
16+8+4+1. Чтобы посчитать распределение бит в 16, делим его на две
части - [0..7] и [8..15]. Замечаем, что во втором интервале [8..15]
распределение бит то-же самое, что и в [0..7] плюс фиксированное кол-во
старших бит (здесь - один). То есть, чтобы посчитать распределение для
всего числа (16) нужно узнать распределение половины интервала. Может
продолжать деление пополам до тех пор, пока не дойдём до единицы. Затем,
предположим у нас есть распределение для [0..7]: {1, 3, 3, 1}, то есть,
было встречено одно 0-битное число, три однобитных, три двухбитных, одно
трехбитное.

отсюда найдем распределение для 16 (сдвигая полученное для 8 вправо на
единицу и суммируя):
{1, 3, 3, 1} + {0, 1, 3, 3, 1} = {1, 4, 6, 4, 1}

Теперь переходим ко второму интервалу (+8), для него нам нужно уже
полученное распределение {1, 4, 6, 4, 1}, его собственное (для 8) {1, 3,
3, 1}, и знание того, что для этого интервала у нас два старших бита
неизменны (маска 10xxx):
Из {1, 3, 3, 1} с учетом одно значащего бита имеем {0, 1, 3, 3, 1},
затем, сложим левый и новый интервалы {1, 4, 6, 4, 1} + {0, 1, 3, 3, 1}
= {1, 5, 9, 7, 2}

и т.д - повторяем шаг алгоритма.

Таким образом мы можем просто перебирать интервалы чисел, отслеживая
значение в распределении в нужной позиции до тех пор, пока не увидим,
что вновь рассмотренный интервал перекрывает искомое число. После этого,
мы можем вернуться обратно к предыдущему интервалу, сократить
просматриваемый интервал в два раза (например - в приведенной интерации,
разбивая интервал 8 на два: 4+4), и опять повторить операцию для
сокращенного интервала. Итерации заканчиваются успехом тогда, когда
завиксирован переход, и длина текущего интервала равна 1 (это будет
искомое число), или мы вышли за заданные границы.
Posted via ActualForum NNTP Server 1.4