Алгоритм поиска простейшей комбинации целых чисел, которая еще не использовалась

Question

Я ищу алгоритм для поиска простейшей комбинации целых чисел от 0 до 5 (то есть той, которая состоит из наименьшего числа целых чисел), которая еще не использовалась (использованные комбинации находятся в списке).

Порядок имеет значение, и комбинации должны быть возвращены в виде списка.

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

{{0}, {1}, {2}, {3}, {4}, {0,0}, {0,1}, {0,2}, ..., {2,1}, {2,2}, ..., {1,5,4}, ...}

В этом случае алгоритм должен вернуть список с {5}, поскольку {5} являетсякомбинация, состоящая из наименьшего числа целых чисел.

Если список выглядит следующим образом:

{{0}, {1}, {2}, {3}, {4}, {5}, {0,0}, {0,1}, {0,2}, {0,3}, {0,5}, ...}

алгоритм должен вернуть список с 0и 4 ({0,4}).

Поскольку он должен использоваться в Java, предпочтительным является ответ Java, но также можно использовать псевдокод или другие языки программирования.

Спасибозаранее!

Answer 1

Полагаю, пример 2 неверен: для {{0}, {1}, {2}, {3}, {4}, {5}, {0,1}, {0,2}, {0, 3}, {0,5}, ...} наименьшее решение - {0,0}, а не {0,4}

Полное решение здесь:

import java.util.*;

public class Algorithm {

    static List<List<Integer>> getChildren(List<Integer> node){
        List<List<Integer>> children = new ArrayList<List<Integer>>();
        for(int i = 0; i < 6; i++){
            List<Integer> child = new ArrayList<Integer>(node);
            child.add(i);
            children.add(child);
        }
        return children;
    }

    static List<Integer> find(Queue<List<Integer>> queue, Set<List<Integer>> set){

        for(;;){
            List<Integer> head = queue.poll();
            if(!set.contains(head)){
                return head;
            } else {
                for(List<Integer> child : getChildren(head)){
                    queue.add(child);
                }
            }
        }
    }

    public static void main(String[] arg) {
        Queue<List<Integer>> queue = new LinkedList<List<Integer>>();
        for(int i = 0; i < 6; i++){
            queue.add(Collections.singletonList(i));
        }
        // Example {{0},{1},{2},{3},{4},{5},{0,1},{0,2},{0,3},{0,5},...}
        Set<List<Integer>> task = new HashSet<List<Integer>>();
        task.add(Arrays.asList(0));
        task.add(Arrays.asList(1));
        task.add(Arrays.asList(2));
        task.add(Arrays.asList(3));
        task.add(Arrays.asList(4));
        task.add(Arrays.asList(5));
        task.add(Arrays.asList(0, 1));
        task.add(Arrays.asList(0, 2));
        task.add(Arrays.asList(0, 3));
        task.add(Arrays.asList(0, 5));

        System.out.println(find(queue, task));
    }

}

Answer 2

Если список, который у вас есть, упорядочен, есть два метода, которые, я думаю, будут лучше, чем линейный поиск.

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

Во-первых, давайте называть каждый набор размера 'x' группой.Итак, 0,1,2,3,4,5 - это группа 1, от {0,0} до {5,5} - это группа 2.

Начиная с группы 1, проверьте позицию списка, содержащуюПоследнее значение в группе, если они все были там.Например, List[5] == 5.Если это так, перейдите к группе 2 и повторите.Если этого не произойдет, выполните бинарный поиск только в этой группе, всегда отдавая предпочтение нижней стороне, в конце концов вы найдете первое пропущенное значение.

---

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

Answer 3

Полное (наивное) решение:

import java.util.*;

public class Test {

    public static String increment(String str) {
        if (str.isEmpty()) return "0";
        int i = str.length() - 1;
        if (str.charAt(i) < '5')
            return str.substring(0, i) + (char) (str.charAt(i) + 1);
        return increment(str.substring(0, i)) + "0";
    }


    public static String nextUnused(Set<String> used) {
        String s = "0";
        while (used.contains(s))
            s = increment(s);
        return s;
    }

    public static void main(String args[]) {
        Set<String> used = new HashSet<String>(Arrays.asList("0", "1", "2", "3",
                "4", "00", "01", "02", "21", "22", "154"));
        for (int i = 0; i < 10; i++) {
            String toUse = nextUnused(used);
            System.out.println("Adding " + toUse);
            used.add(toUse);
        }
    }
}

Вывод:

Adding 5
Adding 03
Adding 04
Adding 05
Adding 10
Adding 11
Adding 12
Adding 13
Adding 14
Adding 15

Вероятно, вы могли бы немного ускорить его, применив памятка кувеличиваем-метод.

Answer 4

Для этой задачи я бы создал конкретный объект для хранения элемента (одно число или кортеж из числа):

class Tuple {
    String key;
    Set<Integer> tuple;
}

Ключом будет порядок упорядочения чисел.В вашем примере ключи будут "0" "1" "2" "3" "4" "5" "01" "02" "03" "05".

Вы можете использовать картудля сохранения кортежей с ключом ассоциации - значение.

Поскольку ключи соответствуют логическому порядку, найти следующий свободный кортеж легко.Вы просто начинаете с «0» и увеличиваете ключ (используя определенный порядок), проверяя на карте, чтобы убедиться, что кортеж уже используется или нет.

В этом примере первый бесплатный кортеж имеет ключ"04".С помощью этого ключа легко создать связанный кортеж.

Answer 5

Просто попробуйте каждую комбинацию по порядку, начиная с самой короткой, и остановитесь, если у вас есть такая, которая не используется?Вы пробовали это, это кажется очень очевидным?