Рубрики

Проверьте, содержит ли двоичная строка все перестановки длины k

Дана двоичная строка и k, чтобы проверить, содержит ли она все перестановки длины k или нет.

Примеры:

Input : Binary string 11001
        k : 2
Output : Yes
11001 contains all possibilities of 
binary sequences with k = 2, 00, 01, 
10, 11

Input : Binary string: 1001
        k : 2
Output: No
1001 does not contain all possibilities of
binary sequences with k = 2. Here 11 
sequence is missing

Объяснение:
В этом примере одна двоичная последовательность длины k не найдена, это 0110.

Таким образом, все двоичные последовательности с k = 4 будут 2 4 = 16. они следуют
0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111,
1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111
Все должны быть подстрокой данной двоичной строки, затем вывести Да, иначе Нет

Алгоритм
Взять двоичную строку и размер k. В двоичной строке мы проверяем, соответствуют ли двоичные последовательности или нет. Двоичная последовательность имеет размер k, так как мы знаем, что в двоичном коде используются 0 и 1 цифра, поэтому для генерации всего двоичных подмножеств используется 2 k элемента. Основная идея заключается в том, чтобы сохранить все двоичные значения в списке в виде строки, а затем сравнить список всех элементов с заданной двоичной строкой в качестве подмножества. Если все встречаются внутри двоичной строки, выведите «Да», в противном случае выведите «Нет».

ДЖАВА

// Java-программа для проверки двоичной строки
// содержит все перестановки длины k.

  

import java.util.*;

public class Checkbinary {

  

    // проверить все перестановки в заданной строке

    public static boolean tocheck(String s, int k)

    {

        List<String> list = BinarySubsets(k);

  

        // чтобы проверить наличие двоичных последовательностей

        // в строке или нет

        for (String b : list) 

            if (s.indexOf(b) == -1)

                return false;        

  

        return true;

    }

  

    // для генерации всех двоичных подмножеств заданной длины k

    public static List<String> BinarySubsets(int k)

    {

        // Объявить список как String

        List<String> list = new ArrayList<>();

  

        // определить формат двоичного файла

        // заданная длина k

        String format = "%0" + k + "d";

  

        // возвращает строковое представление

        // целое число без знака, представленное

        // аргумент в двоичном формате (база 2) с использованием

        // Integer.toBinaryString и конвертировать его

        // в целое число, используя Integer.valueOf.

        // Цикл для 2 <sup> k </ sup> элементов

        for (int i = 0; i < Math.pow(2, k); i++) 

        {

            // Добавить в список все возможное

            // двоичная последовательность заданной длины

            list.add(String.format(format,

                Integer.valueOf(Integer.toBinaryString(i))));

  

            / * Показать все двоичные последовательности данных

               длина к

            System.out.println (String.Format (формат,

            Integer.valueOf (Integer.toBinaryString (я)))); * /

        }

        return list;

    }

  

    // приводной

    public static void main(String[] args)

    {

        String str = "11001";

        int num = 2;

        if (tocheck(str, num))

            System.out.println("Yes");

        else

            System.out.println("No");

    }

}


Выход:

Yes

Рекомендуемые посты:

Проверьте, содержит ли двоичная строка все перестановки длины k

0.00 (0%) 0 votes