Как получить n / 2-значные комбинации из n-значного числа - PullRequest
Новая
       5

Как получить n / 2-значные комбинации из n-значного числа

0 голосов
/ 03 января 2019

Я борюсь с этим алгоритмом.Это должно работать следующим образом:

Если я введу fe 6880, моя программа должна вывести 80 86 80 86 60 68 68.

Как видите, комбинации повторяются.Это потому, что он смотрит на каждую цифру, поскольку это другой объект. В моей программе это правильно.

Вот мой код: 

public static Set<Integer> get2DCombinations(List<Integer> digits) {
    Set<Integer> combinations = new TreeSet<>();

    int t = 0;
    for(Integer i : digits) {
        for (Integer j : digits) {
            t = i * 10 + j;
            if (t / 10 >= 1) {
                combinations.add(t);
            }
        }
    }

    return combinations;
}

Возвращает определенный набор комбинаций, где все комбинации имеют 2 цифры.

Отлично работает, но только с 4-значными числами.Конечно, я могу использовать еще один цикл for-each, но есть ли способ его автоматизировать?

Так что, если я введу 6-значное число, он должен вывести все возможные 3-значные комбинации своих цифр, иесли я введу 8-значный номер, он должен вывести все возможные 4-значные комбинации. Входные числа всегда имеют четное количество цифр.

Не могли бы вы указать мне, как это сделать?

Ответы [ 2 ]

0 голосов
/ 03 января 2019

Вам нужна рекурсивная программа, которая сгенерирует все комбинации для вашего ввода.Вот мое решение.Мой метод принимает String в качестве входных данных (это просто закороченная программа и проще, вы можете адаптировать его к вашим потребностям): 

public static Set<String> get2DCombinations(String input) {
    return backtracking("", input, input.length() / 2) ;
}

public static Set<String> backtracking(String actual, String remaining, int length) {
    if (actual.length() == length) {
        return new HashSet<>(Arrays.asList(actual));
    }

    Set<String> result = new HashSet<>();
    for(int i = 0; i < remaining.length(); i++) {
        result.addAll(backtracking(actual + remaining.charAt(i), remaining.substring(0, i) + remaining.substring(i + 1), length));
    }
    return result;
}

И вы вызываете метод так: 

System.out.println(get2DCombinations(input));

Результат: 

[88, 68, 06, 80, 08, 60, 86]

Как я уже упоминал в комментарии, вам не хватает некоторых комбинаций.Это решение генерирует их все.

0 голосов
/ 03 января 2019

Попробуйте сначала вычислить n / 2.Итак, если n равно 6, то n / 2 = 3. Тогда вы знаете, прежде чем начинать штрафовать комбинации, которые вы ищете комбинации из 3 цифр.Затем вы хотите найти правильный алгоритм, чтобы найти комбинации.Частью решения проблем является разбиение проблем на более мелкие проблемы.Это то, что я сделал здесь.Однако я не могу решить это для вас, потому что вам лучше решать самим, и, во-вторых, есть детали, которые вы не предоставили, поэтому трудно найти правильное решение.

...