Skip to main content
Commonmark migration
Fonte Link

##Preâmbulo

Preâmbulo

##Implementação

Implementação

##Notas finais

Notas finais

##Preâmbulo

##Implementação

##Notas finais

Preâmbulo

Implementação

Notas finais

Fonte Link
afsantos
  • 1,6mil
  • 3
  • 14
  • 18

##Preâmbulo

A resposta já vem tarde, mas talvez ajude alguém na mesma.

Segui o seu exemplo, e usei apenas arrays. Usando classes e objetos é possível limpar um bocado este código. Ao contrário da sua tentativa, esta implementação é iterativa, e, portanto, um pouco mais difícil de compreender.

##Implementação

Segue o método principal, que gera e imprime todas as permutações entre os dois vetores.

private static void permuta(int[] a, int[] b) {
    // p é o tamanho de cada permutação.
    // Começa por permutar um elemento de cada vez,
    // até os permutar todos (vetores originais).
    for (int p = 1, size = Math.min(a.length, b.length); p <= size; ++p) {
        // Listas de índices que vamos permutar em A e B nesta iteração.
        int[] indA = range(p);
        int[] indB = range(p);
        // Este sinal controla quando as permutações esgotam.
        boolean moveuTudo = false;
        while (!moveuTudo) {
            // Faz as permutações para os índices que temos.
            for (int i = 0; i < p; ++i) {
                swap(a, b, indA[i], indB[i]);
            }
            imprime(a, b);
            // Volta a repor tudo no lugar para a próxima volta.
            for (int i = 0; i < p; ++i) {
                swap(a, b, indA[i], indB[i]);
            }
            // Calcula os índices seguintes.
            moveuTudo = atualizaIndices(indB, b.length, p);
            if (moveuTudo) {
                indB = range(p);
                moveuTudo = atualizaIndices(indA, a.length, p);
            }
        }
    }
}

Agora segue a parte mais difícil de entender neste algoritmo, imagino, que é como calcular os índices de permutações em cada iteração. Este método faz isso, e retorna true se já esgotou as possibilidades.

private static boolean atualizaIndices(int[] ind, int n, int p) {
    // Começa por mover o último índice.
    int k = ind.length - 1;
    boolean loop;
    boolean moveuTudo = false;
    do {
        loop = false;
        // Avança o índice.
        ind[k] = ind[k] + 1;
        if (ind[k] > n - (p - k)) {
            // Vai para o índice anterior, se o atual já vai
            // além do tamanho do vetor.
            --k;
            loop = k >= 0;
            moveuTudo = !loop;
        } else {
            // Coloca os índices seguintes à frente do atual.
            for (int k2 = k + 1; k2 < ind.length; ++k2) {
                ind[k2] = ind[k2 - 1] + 1;
            }
        }
    } while (loop);
    return moveuTudo;
}

Para compreender melhor como cheguei a este método, veja esta imagem da Wikipedia, sobre combinações.

algoritmo de combinações

A ideia é igual à forma como estes quadrados vermelhos se deslocam. A diferença, é que neste caso temos dois conjuntos destes quadrados, estes índices, um em cada vetor. Chamei-lhes indA e indB no código.

Só quando o indB esgota os movimentos, é que indA vai para o segundo movimento, e indB volta ao primeiro estado. Isto refere-se a esta parte do código:

            // Calcula os índices seguintes.
            moveuTudo = atualizaIndices(indB, b.length, p);
            if (moveuTudo) {
                indB = range(p);
                moveuTudo = atualizaIndices(indA, a.length, p);
            }

Omiti os métodos range, swap e imprime para não alargar muito a resposta. O primeiro gera um array com números de 0 até p. O segundo troca elementos de dois arrays nas posições especificadas. O terceiro imprime para o ecrã. Nada demais, mas diga-me se quiser que os acrescente.

##Notas finais

Esta implementação gera permutações repetidas, se houver elementos repetidos entre os dois vetores. Se isso for um problema, penso que é mais fácil se implementar as permutações como classes suas, comparáveis, ou usando os conjuntos do java, de modo a que no fim as insira todas num conjunto de permutações (eliminando repetições automaticamente).

Para ver melhor como isto funciona, aprecie um exemplo com os vetores [1,2,3] e [0,0,0]. A escolha dos zeros é para ser mais fácil distinguir os movimentos que acontecem do primeiro vetor para o segundo. Aprecie como se movem da mesma forma que aqueles quadrados vermelhos.

[0, 2, 3] [1, 0, 0]
[0, 2, 3] [0, 1, 0]
[0, 2, 3] [0, 0, 1]
[1, 0, 3] [2, 0, 0]
[1, 0, 3] [0, 2, 0]
[1, 0, 3] [0, 0, 2]
[1, 2, 0] [3, 0, 0]
[1, 2, 0] [0, 3, 0]
[1, 2, 0] [0, 0, 3]
[0, 0, 3] [1, 2, 0]
[0, 0, 3] [1, 0, 2]
[0, 0, 3] [0, 1, 2]
[0, 2, 0] [1, 3, 0]
[0, 2, 0] [1, 0, 3]
[0, 2, 0] [0, 1, 3]
[1, 0, 0] [2, 3, 0]
[1, 0, 0] [2, 0, 3]
[1, 0, 0] [0, 2, 3]
[0, 0, 0] [1, 2, 3]