Алгоритм для нахождения самой простой комбинации целых чисел, которая еще не использовалась
Я ищу алгоритм для нахождения самой простой комбинации целых чисел от 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 предпочтителен, но псевдокод или другие языки программирования применимы также.
Заранее спасибо!
5 ответов
Думаю, пример 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));
}
}
Если список, который у вас есть, упорядочен, я могу придумать два метода, которые лучше, чем линейный поиск.
Предполагая, что вы не полностью заполните пространство комбинаций, вы можете использовать вариант двоичного поиска.
Во-первых, давайте назовем каждый набор размера «x» группой. Итак, 0,1,2,3,4,5 - это группа 1, от {0,0} до {5,5} - группа 2.
Начиная с группы 1, проверьте позицию списка, содержащую последнее значение в группа, если они все были там. Например, List [5] == 5 . Если это так, перейдите к группе 2 и повторите. Если это не так, продолжайте бинарный поиск только в этой группе, всегда отдавая предпочтение нижней стороне, в конечном итоге вы найдете первое отсутствующее значение.
В противном случае, если вы планируете в конечном итоге использовать все пространство комбинаций, просто выполните двоичный поиск по всему пространству комбинаций, проверяя, соответствует ли значение в позиции ожидаемому значению, если все предыдущие значения существовали.
Просто пробуйте каждую комбинацию по порядку, начиная с самой короткой, и останавливайтесь, когда у вас есть та, которая не используется? Вы пробовали, это кажется очень очевидным?
Полное (наивное) решение:
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
Вы, вероятно, могли бы немного ускорить его, применив мемоизацию к методу приращения.
Для этой проблемы я бы создал особый объект для хранения элемента (одного числа или кортежа числа):
class Tuple {
String key;
Set<Integer> tuple;
}
Ключом будет соединение упорядоченных чисел. В вашем примере ключи будут "0" "1" "2" "3" "4" "5" "01" "02" "03" "05".
Вы можете использовать карту для хранения кортежей с ассоциативным ключом-значением.
Поскольку ключи соответствуют логическому порядку, найти следующий свободный кортеж легко. Вы просто начинаете с «0» и увеличиваете ключ (используя определенный порядок), проверяя карту, чтобы проверить, используется ли кортеж уже или нет.
В этом примере первый свободный кортеж имеет ключ «04». С помощью этого ключа легко создать связанный кортеж.