Преобразование императива в декларативный код для непоследовательной реализации

Question

Я хочу знать, как преобразовать мою непоследовательную проблему в декларативную логику.

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

public ArrayList<String> nonconsecutiveOnes(int n){

    ArrayList<String> results = new ArrayList<String>();

        for(int i = 0; i < (int)Math.pow(2,n); i++ ){
            String a= Integer.toBinaryString(i); 
            if (a.contains("11")){
                continue;
            }
            if (a.length() < n)
            {
                char[] c = new char[n- a.length()];

                Arrays.fill(c, '0');
                String zeros = new String(c);

                a = zeros + a;
            }
                results.add(a);
        }
            return results; 
     }     
}

Я уже проверял это. Тем не менее, не пробовал крайние случаи. Все еще нужно, чтобы возвращать ноль, только если длина меньше 1.

Answer 1

Если я правильно понимаю, вас попросят вывести двоичное представление всех чисел меньше 2 ^ n, которое не содержит 2 последовательных 1. Вы можете перефразировать его как все строки из 1 и 0 длиной n, без «11».

Чем вы можете рассматривать это как дерево, где вы выводите его символ за символом, где выпереходите после 0 (чтобы попробовать 0 и 1), но не переходите после 1.

Не уверен, что лямбды, как в java, помогают в ускорении этого.

Но вы можете попытаться решитьэто рекурсивно, что должно привести вас к функциональной реализации.

Например (нет претензий на оптимальность):

public class Ex {

    public static void main(String[] args) {
        printAllStrings(3);
    }

    public static void printAllStrings(int length) {
        printAllStrings("0", length);
        printAllStrings("1", length);
    }

    public static void printAllStrings(String prefix, int length) {
        if (prefix.length() == length) {
            System.out.println(prefix);
        } else {
            printAllStrings(prefix + "0", length);
            if (prefix.endsWith("0")) {
                printAllStrings(prefix + "1", length);
            }
        }
    }
}