Кто-нибудь может объяснить, как этот код генерирует комбинации?

Question

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

import java.util.Collections;
import java.util.LinkedList;

public class Comb{

    public static void main(String[] args){
            System.out.println(comb(3,5));
    }

    public static String bitprint(int u){
            String s= "";
            for(int n= 0;u > 0;++n, u>>= 1)
                    if((u & 1) > 0) s+= n + " ";
            return s;
    }

    public static int bitcount(int u){
            int n;
            for(n= 0;u > 0;++n, u&= (u - 1));
            return n;
    }

    public static LinkedList<String> comb(int c, int n){
            LinkedList<String> s= new LinkedList<String>();
            for(int u= 0;u < 1 << n;u++)
                    if(bitcount(u) == c) s.push(bitprint(u));
            Collections.sort(s);
            return s;
    }
}

Answer 1

Конкретная комбинация группы элементов может быть представлена ​​в виде двоичного числа, где бит n номера представляет, включает ли комбинация элемент # n группы.

Код просто перебирает достаточное количество двоичных чисел для представления всего набора n элементов (от 0 до (1<<n) - 1, что совпадает с 2 ^ n-1), и добавляет каждый, имеющий точно c 1-бит в нем (то есть элементы, которые будут представлены этими битами в заданном комбо) к списку.

Answer 2

Учитывая выбор (r, n), он создаст число n бит шириной, а затем считает от 0 до 2 ^ n.Он проверяет каждое значение, чтобы увидеть, установлено ли у него r битов.Если это так, он добавляет его в качестве допустимой комбинации.С этими числами он формирует допустимые комбинации строк.

Есть намного лучшие алгоритмы для этого.Я предлагаю вам искать в другом месте.