Комбинации логических значений в HashMap Java - PullRequest
Новая
       29

Комбинации логических значений в HashMap Java

0 голосов
/ 09 мая 2018

У меня есть hashmap (Integer, Boolean), а ключи идут от 1 ... N. Я пытаюсь создать метод грубой силы для прохождения каждой комбинации логических выражений, конечная сложность будет O (2 ^ N). Я использую ключи как переменные для своих вычислений, поэтому крайне важно, чтобы логические переменные в изменении хэш-карты не были преобразованы в массив.

Таким образом, хэш-карта размера 4 будет 1 ложь 2 Ложь 3 Неверно 4 Ложь

следующая итерация будет 1 ложь 2 Ложь 3 Неверно 4 True

следующая итерация будет 1 ложь 2 Ложь 3 Правда 4 Ложь

и так далее ...

Ответы [ 2 ]

0 голосов
/ 09 мая 2018

Похоже, что вы хотите перебрать все числа из 1...N и проверить их двоичное представление. Почему вам нужно держать биты? Достаточно просто иметь целое число, и вы всегда сможете преобразовать его в логический массив. Код ниже 

public class BitPlay {
    public static void main(String[] args) {
        for (Integer i = 0; i < 4; i++) {
            System.out.println(Arrays.toString(toBinary(i, 2)));
        }
    }

    private static boolean[] toBinary(int number, int base) {
        final boolean[] ret = new boolean[base];
        for (int i = 0; i < base; i++) {
            ret[base - 1 - i] = (1 << i & number) != 0;
        }
        return ret;
    }
}

Производит: 

[false, false]
[false, true]
[true, false]
[true, true]
0 голосов
/ 09 мая 2018

Вы можете достичь этой функциональности с помощью следующего кода. 

public static void main(String[] args) {
    List<Map<Integer, Boolean>> bitmapList = generateBitMaps(3);

    for (Map<Integer, Boolean> bitmap : bitmapList) {
        System.out.println(bitmap);

    }

}

public static List<Map<Integer, Boolean>> generateBitMaps(int nBits) {
    int size = (int) Math.pow(2, nBits);
    List<Map<Integer, Boolean>> bitmapList = new ArrayList<>(size);

    for (int i = 0; i < size; i++) {
        Map<Integer, Boolean> bitmap = new HashMap<>(nBits);

        int mask = size >> 1;
        int bitId= 1;
        while (mask > 0) {
            if ((mask & i) == 0) {
                bitmap.put(bitId, false);
            } else {
                bitmap.put(bitId, true);
            }
            mask = mask >> 1;
            ++bitId;
        }
        bitmapList.add(i, bitmap);
    }

    return bitmapList;

}

Примечания:

  • Ключи в растровом изображении таким образом, что 1 представляет MSB, а n представляет LSB, как упомянуто в вопросе.
  • Сложность времени O (n * 2 ^ n). ИДК, если это возможно сделать в O (2 ^ n) с картами.
...