Logica de Distribuição Igualada

Question

I was wondering if anyone knows any matching distribution algorithms. For example I have 10 spaces and I have 4 a, 2 b, 3 c, 1 d. And I have to distribute these variables within these 10 positions equally so that they are uniform, without repeating the variables.

---

Example : (A-B-C-A-D-C-A-B-C-A)

Answer 1

I don’t know any formal solution but if I were to "invent" one I would do the following. Use a counter for your list of variables. Looping the list, inserting each variable in the sequence and subtracting the counter.

But then we ended up with

A,B,C,D, A,B,C, A,C, A

for your example. But if we have more A we will get "pairs" of A on the "tail".

To avoid this you can check if the previous variable is equal to the variable being inserted. If yes, go back to the beginning of the sequence and try to enter the position if and only yes the neighbors are different.

If we have 11 positions and one more The sequence would look like this:

A,B, A ,C,D, A,B,C, A,C A

You can try by randomly inserting in the sequence as well but anyway something I see as problematic in this type of algorithm is the "stop", knowing when to give up. For example if you only get A there is no escape from having A,A,A,A,A,A...

Edit

Thinking in a purely random way: For each variable assign a probability of it being inserted, initially equal to its distribution (in example A has a 40% chance of being inserted and D 10%).

Try to enter a variable randomly according to its probability, check the neighbors to see if it is possible. If it is enter and adjust the probability (if I insert the first one as A the probability of next changes from 4/10 to 3/9). If it is not possible to enter, assign zero possibility to that variable and continue. If all variables are "zeroed" check if at some point in the sequence you a "split" solves.

The problem has no solution if there is more than 50% of a variable. In the case of 10 positions it is impossible not to have an AA pair if there is at least 6/10 of A.

A,X,A,X,A,X,A,X,A,A

Answer 2

This problem reminds me of the problem of graph coloring, in which you have to color a number k of vertices using a number n colors, and neighboring vertices cannot have the same colors.

I wouldn’t know how to give a solution right away, but try to study a little about this algorithm that you will surely find a way to solve your problem: http://en.wikipedia.org/wiki/Graph_coloring

Answer 3

I see a solution with Permutation in Combinatorial Analysis.

First we must get the combination of the elements in the example: To₁, To₂, To₃, To₄, B₁, B₂, C₁, C₂, C₃, D₁. Then simply delete those with adjacent identical letters.

Well, permutation has factorial order O(n!) (being n the number of elements) and 10! of the example would generate 3.628.800 of possibilities.

However, we can optimize the algorithm by generating only the combinations that matter, in two ways:

1. Ignoring a combination (and all derived combinations) if the next letter repeats the current one. For example, if we are mounting a combination and we have A, we’ll skip the combination AA and all its derivations (AAB, AAC, ...).
2. Ignoring iterations with repeated letters. Although we have 4 letters To, we don’t need to test the combinations starting with all of them. We only need to test one element corresponding to each letter.

To tell you the truth I don’t know how to analyze the order of complexity of this optimization, but what I can say is that the more repeat items there are, the less possibilities will be tested and the faster we will get the result.

Being m the number of letters (ignoring the repetition) and n the total number of elements (counting the repeated ones), we can say that, in the worst case, if we have an element of each letter (m == n), the algorithm will be effectively O(n!). But if we have repetition (m < n), the complexity will be greater than O(m!) and less than O(n!).

I made the following implementation in Java:

public class Distribuicao {

    private List<String> combinacoes = new ArrayList<String>();
    private List<String> becos = new ArrayList<String>();
    private long combinacoesTestadas = 0;

    /**
     * Começa pegando as letras uma a uma e combinando o restante.
     * Note que assim já não precisamos verificar as combinações repetidas,
     * já que usamos a chave única do mapa. 
     */
    public Distribuicao(HashMap<Character, Integer> itens) {
        for (Entry<Character, Integer> e : itens.entrySet()) {
            trocarECombinar(itens, e, "");
        }
    }

    /**
     * Procura novas combinações, ignorando se repetir a letras
     */
    private void combinar(HashMap<Character, Integer> itens, String prefixo) {
        Character ultimo = prefixo.charAt(prefixo.length() - 1);
        boolean itensSobrando = false;
        boolean encontrouNovaPossibilidade = false;
        //verifica cada letra, sem repetir
        for (Entry<Character, Integer> e : itens.entrySet()) {
            //verifica se ainda há um elemento disponível da letra
            if (e.getValue() > 0) {
                itensSobrando = true;
                //verifica se é igual à anterior
                if (!e.getKey().equals(ultimo)) {
                    encontrouNovaPossibilidade = true;
                    //tenta uma nova combinação com a letra atual
                    trocarECombinar(itens, e, prefixo);
                }
            }
        }
        if (!itensSobrando) {
            combinacoesTestadas++;
            combinacoes.add(prefixo);
        } else if (!encontrouNovaPossibilidade) {
            combinacoesTestadas++;
            becos.add("[prefixo = " + prefixo + ", resto = " + itens + "]");
        }
    }

    /**
     * Decrementa a letra usada, acrescenta a atual no prefixo
     * e tenta recursivamente uma nova combinação 
     */
    private void trocarECombinar(
            HashMap<Character, Integer> itens,
            Entry<Character, Integer> e,
            String prefixo) {
        e.setValue(e.getValue() - 1);
        combinar(itens, prefixo + e.getKey().toString());
        e.setValue(e.getValue() + 1);
    }

    public List<String> getCombinacoes() {
        return combinacoes;
    }

    public List<String> getBecos() {
        return becos;
    }

    public long getCombinacoesTestadas() {
        return combinacoesTestadas;
    }

    public static void main(String[] args) {

        //prepara o mapa de teste
        HashMap<Character, Integer> mapa = new HashMap<Character, Integer>();
        mapa.put('A', 4);
        mapa.put('B', 2);
        mapa.put('C', 3);
        mapa.put('D', 1);

        //executa a distribuição
        Distribuicao d = new Distribuicao(mapa);

        //quantidade de combinações testadas
        System.out.println("Combinações testadas: " + d.getCombinacoesTestadas());

        //combinações encontradas 
        System.out.println("Combinações encontradas: " + d.getCombinacoes().size());
        for (String combinacao : d.getCombinacoes()) {
            System.out.println("  -> " + combinacao);
        }

        //combinações onde não houve como continuar     
        System.out.println("Becos sem saída: " + d.getBecos().size());
        for (String beco : d.getBecos()) {
            System.out.println("  -> " + beco);
        }

    }

}

In the example, we have n = 10 and m = 4. This is consistent with the return of the algorithm:

• 1074 combinations
• 462 ""dead ends, that is, situations where there were no letters available to continue and the process was stopped