Сгенерировать все двоичные вектора длины 32 весом n <= 4

Question

Никак не могу решить это задание. Все другие решения, которые я нашел, работают на меньшую длину - при длине 32 они, как правило, перестают работать правильно, поэтому я не рассматриваю этот вопрос как дубликат других - очень важно, чтобы алгоритм работал именно с такой длиной

Насколько я понимаю, что-то происходит с определением "фиксированных" битов и двигающихся битов на каждой итерации. Проще показать на примере (здесь длина 5 - 32 слишком длинна, чтобы писать здесь):

1 1 1 0 0
1 1 0 1 0 // сдвинуть последний бит дальше
1 1 0 0 1
1 0 1 1 0 // попробовать для других перестановок
1 0 1 0 1
1 0 0 1 1
0 1 1 1 0 // сдвинуть первый бит
0 1 1 0 1
0 1 0 1 1
0 0 1 1 1

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

Answer 1

Вот так можно перечислить все слова длиной n с k установленными битами

    int k = 2;
    int n = 4;
    int v = (1 << k) - 1;
    int finish = v << (n - k);
    вывести v;
    while (v != finish) {
        int t = (v | (v - 1)) + 1;  
        v = t | ((((t & -t) / (v & -v)) >> 1) - 1); 
        вывести v;
    }

Для n=4,k=2 выводит набор 3,5,6,9,10,12

В вашем случае n=32, k меняете от 0 или 1 до 4

По ссылке есть метод без деления, но с использованием builtin_ctz()/_BitScanForward/BSF

Answer 2

Суть состоит в том, что даже если будешь генерировать следующую пермутацию (перестановку) за наносекунду, ты всё равно потратишь огромную кучу времени на вывод результатов твоего алгоритма на экран. Я пришёл к такому рекурсивному алгоритму:

void gen_Binary(int* vector, int level, int frozen) // глубина рекурсии (первое значение равно 1), замороженные (красные) позиции
{                                                   
    while (frozen < SIZE)                           // SIZE - int длина вектора
    {
        vector[frozen] = 1;

        if (level != N)
            gen_Binary(vector, level + 1, frozen + 1); // генерируем все возможные пермутации при единице на первом индексе (и т.д)

        // Этот кусок кода с циклом for замедлит программу в десяток раз
        printf("\n");
        for (int i = 0; i < SIZE; i++)
            printf(" %d ", vector[i]);

        vector[frozen] = 0;                           // поставим единицу на второй индекс
        frozen++;
    }
}

Преподаватель примет работу, если доказать, что

Алгоритм верен
Алгоритм оптимален.

Затем достаточно сделать правильный вывод: printf может крайне существенно замедлить программу Вот древо рекурсии для N = 2 (сначала выводятся 0 0 0 0, 1 0 0 0, затем 1 1 0 0 и 1 0 1 0 и т.д):

БЛОГ НА HUSL

Сгенерировать все двоичные вектора длины 32 весом n <= 4

Ответы (2 шт):