Permutation between two vectors

Question

Permutation between two vectors

Navigation

#1 by (4 votes)

6

I'm studying some algorithm techniques and I came across a problem that I'm stuck in, I need to do all the permutation possibilities between two vectors. For example:

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

You need to 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 this what I have achieved so far is to make a permutation between the same vector recursively.

Passing a vector [1,2,3]. Generate response: 123 132 213 231 321 312

It is the code 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 do the permutation between the two vectors?

java

asked by anonymous 29.08.2015 / 22:41

1 answer

Servlet Doubt Code block freezing and not throwing exception

score 4 · Accepted Answer

Preamble

The answer is late, but maybe it helps someone in it.

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

Implementation

Here is 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 follows the harder part of understanding this algorithm, I imagine, which is how to calculate the permutation indices at each iteration. This method does this, and returns true if it has already exhausted the possibilities.

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 from Wikipedia, about combinations .

The idea equals the way these red squares 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 indA goes to the second movement, and indB returns 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 have omitted the methods range , swap and imprime so as not to extend the response too much. The first generates an array with numbers from 0 to p . The second exchange elements of two arrays in the specified positions. The third prints to the screen. Nothing much, but let me know if you'd like me to add them.

Final notes

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 their classes, comparable, or using the java sets, so that in the end they all insert them into a set of permutations (eliminating repetitions automatically). >

To better see how this works, consider an example with the [1,2,3] and [0,0,0] vectors. 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 in 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]