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.
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]
[1, 3, 2]
e[5, 7, 6]
seria uma permutação válida ou só são validas permutações em que um membro do primeiro vetor é trocado com outro do segundo?[5, 2, 3], [1,6,7]
é diferente de[1,6,7], [5, 2, 3]
?