Equal Distribution Logic

This problem reminds me of the coloring of graphs problem, in which you have to color a% number of vertices using a% color number, and neighboring vertices can not have the same colors.

I would not know how to give a face-to-face solution, but try to study a little bit about this algorithm, which is sure to find a way to solve your problem: link

I do not know any formal solution but if I were to "invent" one would do the following. Use a counter for your list of variables. Loop through the list by inserting each variable in the sequence and subtracting the counter.

But then we end up with

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

for your example. But if we have more A we will have pairs of A in 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 insert in the position if and only if the neighbors are different.

In case we have 11 positions plus one A the sequence would look like this:

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

You can try is inserting randomly in the sequence too 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 receive A there is no escape from having A, A, A, A, A ...

Edit

Thinking in a purely random way: For each variable, give it a probability of being inserted, first equal to its distribution (in example A has 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 I enter and adjust the probability (if I enter 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 the variables are "zeroed" check that at some point in the sequence you split.

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

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

I see a solution with Simple Permutation in Combinatorial Analysis .

First we should get the combination of the elements in the example: A 1 , A 2 , > 3 C 2 , C 1 C 3 , D 1 . Then delete the ones that have adjacent equal letters.

Well, the permutation has a 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 only generating the combinations that matter, in two ways:

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

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

I made the following Java implementation:

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 O(n!) and n = 10 . This is consistent with the algorithm's return:

• m = 4 combinations
• % with "dead ends", ie situations where there were no letters available to continue and the process was interrupted