Permutation between two vectors

Question

I’m studying some algorithmic techniques and I came across a problem that I’m stuck with, I need to make all the possibilities of permutation between two vectors. For example:

[1,2,3] and [5,6,7]

Must generate:

[123] and [567]

[125] and [367]

[126] and [537]

[127] and [563]

[135] and [267]

[136] and [267]

[137] and [256]

[156] and [237]

[157] and [236]

[167] and [235]

From that point on what I’ve achieved so far is to permute between the same vector recursively.

Passing a vector [1,2,3]. Generates the answer: 123 132 213 231 321 312

The code is below:

public void permutar(int[] num, int idx) {
    for (int i = idx; i < num.length; i++) {
        swap(num, i, idx);
        permutar(num, idx + 1);
        swap(num, i, idx);
    }
    if (idx == num.length - 1) {
        for (int i = 0; i < num.length; i++) {
            System.out.print(num[i]);
        }
        System.out.println("");
    }
}

public void swap(int[] num, int a, int b) {
    int aux = num[a];
    num[a] = num[b];
    num[b] = aux;
}

Does anyone know how to permute between the two vectors?

Answer 1

Preamble

The answer comes late, but maybe it helps someone anyway.

I followed his example, and used only arrays. Using classes and objects it is possible to clean this code a bit. Unlike your attempt, this implementation is iterative, and therefore a little more difficult to understand.

Implementation

Follows the main method, which generates and prints all permutations between the two vectors.

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);
            }
        }
    }
}

Now it follows the most difficult part to understand in this algorithm, I imagine, which is how to calculate the permutation indices in each iteration. This method does this, and returns true if the possibilities are exhausted.

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;
}

To better understand how I came to this method, see this image of Wikipedia, about combinations.

The idea is the same as how these red squares get move. The difference is that in this case we have two sets of these squares, these indices, one in each vector. I called them indA and indB in the code.

Only when the indB depletes the movements, is that indA goes into the second movement, and indB back to the first state. This refers to this part of the code:

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

I omitted the methods range, swap and imprime not to extend the answer too much. The first generates an array with numbers from 0 to p. The second exchanges elements of two arrays at the specified positions. The third prints to the screen. No big deal, but let me know if you want me to add them.

Endnotes

This implementation generates repeated permutations if there are repeated elements between the two vectors. If this is a problem, I think it is easier to implement the permutations as comparable classes of yours, or using the java sets, so that in the end you insert them all into a set of permutations (eliminating repetitions automatically).

To better see how this works, enjoy an example with the vectors [1,2,3] and [0,0,0]. The choice of zeros is to be easier to distinguish the movements that happen from the first vector to the second. Enjoy how they move the same way as those red squares.

[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]