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

Возможный дубликат:
Создание нескольких номеров с определенным количеством бит, установленным

Я пытаюсь написать некоторый код, который поместит каждую возможную комбинацию чисел в массив, сдвинув биты.

Например, я хотел найти все возможные комбинации из 3 бит (где максимальная цифра может быть равна 6), массив должен содержать:

И так далее...

Из того, что я интерпретировал, когда бит последней позиции равен 1, мы сдвигаем число на 1 (x → 1) и добавляем 1 в начале. Однако я не уверен, как закодировать остальные. Я использую C, чтобы написать это.

Кроме того, насколько я могу судить, это последовательность colex, однако, я все уши, если есть другая последовательность, которая даст мне тот же конечный результат (массив со всеми возможными комбинациями k-бит с ограничением из N).

Ответы

Ответ 1

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

Определим рекурсивную функцию 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

Ответ 2

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

    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

Приятно и легко.

Ответ 3

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