Побитовый сдвиг для создания всех возможных перестановок в C

Вы можете решить эту проблему, рекурсивно генерируя последовательности.

Давайте определим рекурсивную функцию f(int index, int bits, int number), которая будет принимать текущие index бита и количество bits, оставшихся для размещения, и number, сгенерированных на данный момент. Затем у вас есть возможность установить для текущего бита значение 1 или 0 и выполнить рекурсию оттуда.

В целом, временная сложность должна быть O (количество последовательностей) или O (N выбирает B), где N — количество цифр, а B — количество битов, установленных на 1.

Функция выглядит примерно так:

void f(int index, int bits, int number) {
    if (index == 0) {
        if (bits == 0) {   // all required bits have been used
            emit_answer(number); // chuck number into an array, print it, whatever.
        }   
        return;
    }   

    if (index-1 >= bits) {  // If we can afford to put a 0 here
        f(index-1, bits, number);
    }   

    if (bits > 0) {  // If we have any 1s left to place
        f(index-1, bits-1, number | (1 << (index-1)));
    }   
}

// to call:
f(6, 3, 0); 

Для N,B = 6,3 выходные данные совпадают с вашими и отсортированы. Ссылка на рабочий пример: http://codepad.org/qgd689ZM

Вероятно, есть более эффективный способ, но вы могли бы просто перебрать числа и отклонить числа, у которых битовое число не равно 3? См. этот ответ для подсчета битов.

Нет необходимости в какой-либо причудливой рекурсии. Достаточно простой математики (требуется деление на значение, которое всегда будет степенью двойки).

    Function nextBits(ByVal prevVal As Integer)
        Dim lsOne As Integer = ((prevVal - 1) And Not prevVal) + 1
        Dim nextZero As Integer = (prevVal + lsOne) And Not prevVal
        Dim lowBits As Integer = ((nextZero \ lsOne \ 2) - 1)
        Return prevVal + lsOne + lowBits
    End Function

Легко и приятно.