## 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][1] da Wikipedia, sobre combinações.

[![algoritmo de combinações][2]][2]

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]: https://en.wikipedia.org/wiki/File%3ACombinations_without_repetition;_5_choose_3.svg
  [2]: https://i.sstatic.net/aomLC.png