Algoritmo para encontrar a combinação mais simples de inteiros que ainda não foi usada

9

Estou procurando um algoritmo para encontrar a combinação mais simples de inteiros de 0 a 5 (que é o que consiste no menor número de inteiros) que ainda não foi usado (as combinações usadas estão em uma lista).

A ordem importa e as combinações devem ser retornadas em uma lista.

Por exemplo, a lista com os números usados poderia ser assim:

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

Nesse caso, o algoritmo deve retornar uma lista com {5}, pois {5} é a combinação que consiste no menor número de inteiros.

Se a lista estiver assim:

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

o algoritmo deve retornar uma lista com 0 e 4 ({0,4}).

Como é para ser usado em Java, uma resposta Java é preferível, mas pseudo-códigos ou outras linguagens de programação também são utilizáveis.

Obrigado antecipadamente!

    
por akaloer 23.07.2010 в 09:56
fonte

5 respostas

2

Eu acho que o exemplo 2 está errado: para {{0}, {1}, {2}, {3}, {4}, {5}, {0,1}, {0,2}, {0,3}, {0,5}, ...} a menor solução é {0,0}, não {0,4}

Soluções completas estão aqui:

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));
    }

}
    
por Nulldevice 23.07.2010 / 11:29
fonte
2

Se a lista que você tem é ordenada, existem dois métodos que eu acho que seria melhor do que uma pesquisa linear.

Supondo que você não preencherá completamente o espaço de combinação, poderá usar uma variação de uma pesquisa binária.

Primeiro, vamos chamar cada conjunto de tamanho 'x' de um grupo. Assim, 0,1,2,3,4,5 é o grupo 1, {0,0} a {5,5} é o grupo 2.

Começando com o grupo 1, verifique a posição da lista que contém o último valor no grupo, se todos estiverem lá. Por exemplo, List[5] == 5 . Se isso acontecer, vá para o grupo 2 e repita. Se isso não acontecer, faça uma busca binária dentro desse grupo sempre favorecendo o lado inferior, eventualmente você encontrará o primeiro valor perdido.

Caso contrário, se você espera usar todo o espaço da combinação, faça uma pesquisa binária em todo o espaço da combinação, verificando se o valor na posição corresponde ao valor esperado, se todos os valores anteriores existirem.

    
por Dan McGrath 23.07.2010 / 10:07
fonte
1

Uma solução completa (ingênua):

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);
        }
    }
}

Saída:

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

Você provavelmente poderia acelerar um pouco aplicando a memoização ao método de incremento.

    
por aioobe 23.07.2010 / 10:06
fonte
0

Apenas tente cada combinação em ordem, começando com a mais curta, e pare quando tiver uma que não seja usada? Você tentou isso, parece realmente óbvio?

    
por Kieren Johnstone 23.07.2010 / 09:59
fonte
0

Para esse problema, criaria um objeto específico para armazenar um elemento (número único ou tupla de numer):

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

A chave seria a contatenação dos números, ordenada. No seu exemplo, as chaves seriam "0" "1" "2" "3" "4" "5" "01" "02" "03" "05".

Você pode usar um mapa para armazenar as tuplas, com o valor-chave da associação.

Como as chaves respeitam uma ordem lógica, é fácil encontrar a próxima tupla livre. Você acabou de começar com "0" e incrementa a chave (usando a ordem definida), checando o mapa para verificar se a tupla já está sendo usada ou não.

Neste exemplo, a primeira tupla livre possui a chave "04". A partir dessa chave, criar o Tuple associado é fácil.

    
por Benoit Courtine 23.07.2010 / 10:05
fonte