Алгоритм вычисления последовательностей нулей и единиц в заданном порядке c

Question

Я пытаюсь написать алгоритм next() для вычисления следующей последовательности со следующими правилами порядка:

1. Все последовательности имеют длину n и состоят из 0 s и 1 s.

2. Последовательность с меньшим 1 s будет перед последовательностью с большим 1 s

3. Последовательность с более 1 s слева будет перед последовательностью с меньшим 1 s слева среди последовательностей с таким же количеством 1 s (т. Е. Если сравнивать элемент за элементом слева направо , первый будет иметь 1, а другой - 0 будет первым)

Результат для n=4 при вызове next() 15 раз будет be:

0000
1000
0100
0010
0001
1100
1010
1001
0110
0101
0011
1110
1101
1011
0111
1111

Каждый вызов next() должен обновлять переменную stati c для хранения последнего результата. первая последовательность 0 s будет сгенерирована заранее и должна исправить длину.

Я пытаюсь реализовать это в Java, поэтому я бы предпочел найти ее в Java, хотя это не критически важно, так как основная проблема - это лог c.

Моя основная идея заключалась в том, чтобы сместить крайний правый 1, но основная проблема заключается в том, как справиться со случаем, когда в крайняя правая позиция, и я не могу понять, как двигаться дальше, исходя из этих случаев.

Это моя попытка, но она может иметь некоторую aws, которую я не знаю, как отлаживать. Кроме того, я думаю, что это можно сделать лучше, чем то, что я сделал здесь:

public static int[] next() {
    int i = last_res.length - 1;
    while (i >= 0) {
        if (last_res[i] == 1) {
            last_res[i] = 0;
            if (i + 1 < last_res.length) {
                last_res[i + 1] = 1;
                return last_res;
            } else {
                i--;
                while (i >= 0) {
                    if (last_res[i] == 1) {
                        last_res[i + 1] = 1;
                        return last_res;
                    }
                    i--;
                }
            }
        }
        i--;
    }
    last_res[0] = 1;
    return last_res;
}

Спасибо

Answer 1

Это очень чистое решение, но вы рассчитаете все значения заранее, поэтому, если производительность является проблемой, следует рассмотреть другой подход.

    public static void main(String[] args) {
        final int size = 4;
        List<String> results = new ArrayList<>();
        for (int i = 0; i <= size; i++) {
            calculateChances(size - i, i, "", results);
        }
        results.stream().forEach(System.out::println);
    }

    public static void calculateChances(int zeroes, int ones, String current, List<String> results) {
        if (zeroes == 0 && ones == 0) {
            results.add(current);
            return;
        }
        if (ones > 0) {
            calculateChances(zeroes, ones - 1, current + "1", results);         
        }
        if (zeroes > 0) {
            calculateChances(zeroes - 1, ones, current + "0", results);         
        }       
    }

Если вам нужна простая реализация следующего, вы можете просто создать итератор из списка результатов.

Answer 2

Это решит вашу проблему - но там нет рекурсии: -)

Плюс нет переменной stati c для текущего значения - вместо этого я бы передал текущее значение для вычисления следующего .. ... но, возможно, это поможет вам в решении вашей задачи.

    public static void main(String... args) {
        int n = 10;         
        //if n was dynamic, you'd compute that to have exact number.
        String current = leastSignificantForN(n, 0); 
        while(countOnes(current) < n) {
            System.out.println(current);
            current = next(current);
        }
        System.out.println(current);
    }

    private static String next(String current) {
        long co = countOnes(current);
        if(isMostSingificantForN(current, co)) {
            return leastSignificantForN(current.length(), co+1);
        } else {
            return increaseSignificance(current);
        }
    }

    private static String increaseSignificance(String current) {
        //Look for "moveable" 1
        int idx = current.lastIndexOf("01");
        StringBuilder sb = new StringBuilder();
        //Kepp string to the left intact
        for(int i = 0; i < idx; ++i) {
            sb.append(current.charAt(i));
        }
        sb.append("10");
        for(int i = idx + 2; i < current.length(); ++i) {
            sb.append(current.charAt(i));
        }
        return sb.toString();
    }

    private static String leastSignificantForN(int targetLength, long length) {
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < targetLength - length; ++i) {
            sb.append('0');
        }
        for(int i = 0; i < length; ++i) {
            sb.append('1');
        }
        return sb.toString();
    }

    private static boolean isMostSingificantForN(String current, long co) {
        int pos = 0;
        int count = 0;
        while(pos < current.length() && current.charAt(pos++) == '1') {
            ++count;
        }
        return count == co;
    }

    private static long countOnes(String current) {
        return current.chars().filter(i -> '1' == i).count();
    }