2 Power of 77 Java Powerset

Question

У меня есть 77 элементов n1,n2,n3... и т. Д. Мне нужно рассчитать суперсет. Я использовал алгоритм двоичной маски, но число слишком велико, чтобы поместиться в int. Вот код:

private static Vector powerset(String[] set) {

       //create the empty power set
       Vector power = new Vector();

       //get the number of elements in the set
       int elements = set.length;

       //the number of members of a power set is 2^n
       int powerElements = (int) Math.pow(2,elements);

       //run a binary counter for the number of power elements
       for (int i = 0; i < powerElements; i++) {

           //convert the binary number to a string containing n digits
           String binary = intToBinary(i, elements);

           //create a new set
           Vector innerSet = new Vector();

           //convert each digit in the current binary number to the corresponding element
            //in the given set
           for (int j = 0; j < binary.length(); j++) {
               if (binary.charAt(j) == '1')
                   innerSet.add(set[j]);
           }

           //add the new set to the power set
           power.add(innerSet); 
       }
       return power;
   }
   private static String intToBinary(int binary, int digits) {

       String temp = Integer.toBinaryString(binary);
       int foundDigits = temp.length();
       String returner = temp;
       for (int i = foundDigits; i < digits; i++) {
           returner = "0" + returner;
       }

       return returner;
   } 

Я пытался удалить int с помощью long или double, но ничего не получалось.

Answer 1

Из комментариев становится ясно, что это найти максимальную клику, поэтому сейчас я сосредоточусь на этом, а не на буквальном вопросе.

Сначала несколько простых трюков. Благодаря обратному отслеживанию многие ветви пространства поиска могут быть сокращены. Грубая идея выглядит

findMaxClique(clique, banned, graph):
    if clique ∪ banned is everything:
        if isclique(clique) and size(clique) > size(bestFound):
            bestFound = clique
        return
    for each node n not in clique ∪ banned:
        try findMaxClique(clique + n, banned, graph)
        try findMaxClique(clique, banned + n, graph)

Это все еще наивная версия, пробующая все возможные варианты. Но есть некоторые очевидные улучшения. Например, нет смысла ждать, чтобы проверить, является ли потенциальная клика на самом деле кликой, до последнего момента каждое подмножество узлов, образующих клику, также образует клику. Добавление узла, который не оставляет клики, бессмысленно. Назовите это # ​​1. Это много чернослива.

Кроме того, если текущая клика плюс возможные к ней узлы меньше, чем лучшая найденная клика, в этой ветви пространства поиска ничего лучше найти нельзя. Здесь вы можете сделать несколько разных уровней усилий, самый простой - просто посчитать все в оставшемся наборе, но вы можете выбрать самую большую клику в этом наборе или что-то в этом роде. В любом случае, я покажу простой, назовите это # ​​2. Теперь у нас есть что-то вроде:

findMaxClique(clique, banned, graph):
    if clique ∪ banned is everything:
        if size(clique) > size(bestFound):
            bestFound = clique
        return
    for each node n not in clique ∪ banned:
        if isclique(clique + n):
            try findMaxClique(clique + n, banned, graph)
        notbanned = graph - (banned ∪ n)
        if size(notbanned) >= size(bestFound):
            try findMaxClique(clique, banned + n, graph)

Другой вариант оценки размера клики, который вы можете создать, - использовать линейное программирование.

Например, это модель ILP для максимальной клики:

maximize sum x[i]
s.t.
for each i,j that are not adjacent, x[i]+x[j] ≤ 1
x[i] in { 0, 1 }

Линейная релаксация (т.е. удаление последнего ограничения) легко вычисляется, и вы можете лениво добавлять ограничения, если хотите. Очевидно, что существуют ограничения clique/banned устанавливает, заставляя определенные x быть 1 или 0 соответственно. Если объективное значение линейной релаксации не лучше, чем ваша самая большая найденная клика, то вы можете обрезать текущую ветвь.

Есть еще одно забавное свойство этой модели. Если результирующий x имеет все записи из {0, 0.5, 1}, то вы можете сразу решить выбрать все узлы, для которых x[i] = 1, в вашей клике, так что вы можете пропустить много ветвлений в этом случае., Это, вероятно, необычно высоко в дереве поиска, но вы можете добавить некоторые сокращения Гомори, чтобы поощрить целостность. Ваш любимый решатель LP может иметь встроенные.

Здесь есть более умные трюки, проверьте литературу.

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

for each i,j that are not adjacent: ¬i + ¬j ≥ 1
sum of everything = k

Обычное ограничение смежности тривиально для состояния в чистом SAT, ограничение суммы раздражает, требуя схемы сложения. Это достаточно просто генерировать, но сложно написать здесь, не только потому, что это зависит от k.

Answer 2

Вам нужна структура данных, хранящая двоичные цифры длиной 77 цифр. Вы можете использовать массив из 77 дюймов и вручную увеличивать массив как одно большое двоичное число, где каждый элемент массива занимает один бит в вашем числе. Я написал метод приращения ниже.

int[] num = new int[77];
for (int i = 0; i < 77; i++) num[i]= 0;
//create a new set
for (int i = 0; i < powerElements; i++) {
    Vector innerSet = new Vector();

    for (int j = 0; j < 77; j++) {
        if (num[i] == 1)
            innerSet.add(set[j]); 
    }
    Increment(num);
}

// Increment an array of ints as if it is a binary number. The LSB is the 77th element in the array, index 76.
public void Increment(int[] num) {
    int carry = 1;
    int i = 76;
    while (i > 0) {
        tmp = int[i] + carry;
        if (tmp == 0) break;
        if (tmp == 1) {int[i] = 1; break;}
        carry = 1;
        int[i] = 0;
        i--;
    }
    if (carry == 1) throw new Exception("Overflow");
}

Как отмечают комментаторы, у вас не будет места для хранения 2^77 комплектов. И для подсчета до 2^77 потребуется практически вечность.