0

I´m studying some techniques of algorithms and got stucked in one problem, I need to do a permutation between two groups. For example:

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

Need to generate:

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

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

........

And so on.

From this what I've done so far is do a permutation in one vector between yourself.

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

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

How to do a permutation between this two vectors?

Nicolas Bontempo
  • 181
  • 1
  • 11
  • You could just use it as one vector, either by really putting them into one vector or by a getter which chooses vector 1 or vector 2 depending on the number, and then permutate. – flaschenpost Aug 29 '15 at 22:26
  • 1
    What's the difference between permutations of [1,2,3]e[5,6,7] and [1,2,3,5,6,7]. Aren't you simply doing permutations of 6 numbers? – Andreas Aug 29 '15 at 22:26
  • @flaschenpost Two minds, one thought :-) – Andreas Aug 29 '15 at 22:27
  • I can´t use simple like one vector because I don´t want to spend computacional processing doing a permutation between 1,2,3, I only can permutate between the two vectors. With this [2,1,3] and [5,6,7] is not a valid permutation. – Nicolas Bontempo Aug 29 '15 at 22:35
  • But `[1,2,5] e [5,3,7]` would be valid? And this would be the same as `[1,5,2] e [5,3,7]` or `[1,2,5] e [5,7,3]`, right? That is, the *positions* do not matter - you just want all combinations where the elements are either left or right? (I also don't know an easy description or an appropriate term for this right now...) – Marco13 Aug 29 '15 at 23:21
  • 1
    If @Marco13 is right, you can use bitwise representation. i.e. 000 means `[1,2,3] e [5,6,7]` ; 101 means `[5,2,7] e [1,6,3]` . You generate all of these just by going from `0` to `n` – Václav Blažej Aug 29 '15 at 23:24
  • @VáclavBlažej That's what my question was aiming at. If it can be simplified to "each element can either be left or right", then the solution may be given by a few binary numbers, interpreted appropriately. – Marco13 Aug 29 '15 at 23:27
  • First I can´t repeat the terms in left and right like this 5, but yes the positions dont matter, all that matter is the combination. – Nicolas Bontempo Aug 29 '15 at 23:29
  • If you merge both vectors into one and generate all combinations of 3 elements, then this is possibly related: http://stackoverflow.com/questions/4504974/how-to-iteratively-generate-k-elements-subsets-from-a-set-of-size-n-in-java – afsantos Sep 16 '15 at 15:24

3 Answers3

2

Although you did not precisely describe what you are looking for, and attempt to answer: It seems like you are just looking for all 3-element subsets of the input (1,2,3,5,6,7). Each subset is the first vector of one solution, and the respective remaining elements the other vector.

Here is an example how this may be computed, based on a ChoiceIterable utility class that I wrote a while ago:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.Set;

public class CombinationsOfVectors
{
    public static void main(String[] args)
    {
        List<Integer> input = Arrays.asList(1,2,3,5,6,7);

        ChoiceIterable<Integer> c = new ChoiceIterable<Integer>(3, input);
        for (List<Integer> v0 : c)
        {
            Set<Integer> s = new LinkedHashSet<Integer>(input);
            s.removeAll(v0);
            List<Integer> v1 = new ArrayList<Integer>(s);

            System.out.println(v0+" and "+v1);
        }
    }
}


// From https://github.com/javagl/Combinatorics/blob/master/src/
// main/java/de/javagl/utils/math/combinatorics/ChoiceIterable.java
// See the GitHub repo for a commented version
class ChoiceIterable<T> implements Iterable<List<T>>
{
    private final List<T> input;
    private final int sampleSize;
    private final long numElements;
    public ChoiceIterable(int sampleSize, List<T> input)
    {
        this.sampleSize = sampleSize;
        this.input = input;
        long nf = factorial(input.size());
        long kf = factorial(sampleSize);
        long nmkf = factorial(input.size() - sampleSize);
        long divisor = kf * nmkf;
        long result = nf / divisor;
        numElements = result;    
    }
    private static long factorial(int n)
    {
        long f = 1;
        for (long i = 2; i <= n; i++)
        {
            f = f * i;
        }
        return f;
    }    
    @Override
    public Iterator<List<T>> iterator()
    {
        return new Iterator<List<T>>()
        {
            private int current = 0;
            private final int chosen[] = new int[sampleSize];
            {
                for (int i = 0; i < sampleSize; i++)
                {
                    chosen[i] = i;
                }
            }
            @Override
            public boolean hasNext()
            {
                return current < numElements;
            }

            @Override
            public List<T> next()
            {
                if (!hasNext())
                {
                    throw new NoSuchElementException("No more elements");
                }

                List<T> result = new ArrayList<T>(sampleSize);
                for (int i = 0; i < sampleSize; i++)
                {
                    result.add(input.get(chosen[i]));
                }
                current++;
                if (current < numElements)
                {
                    increase(sampleSize - 1, input.size() - 1);
                }
                return result;
            }

            private void increase(int n, int max)
            {
                if (chosen[n] < max)
                {
                    chosen[n]++;
                    for (int i = n + 1; i < sampleSize; i++)
                    {
                        chosen[i] = chosen[i - 1] + 1;
                    }
                }
                else
                {
                    increase(n - 1, max - 1);
                }
            }

            @Override
            public void remove()
            {
                throw new UnsupportedOperationException(
                    "May not remove elements from a choice");
            }
        };
    }
}

The output in this example will be

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

If this is not what you have been looking for, you should describe more clearly and precisely what the intended result is.

(E.g. whether or not

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

and

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

count as different results is up to you, but you may filter the results accordingly)

Marco13
  • 53,703
  • 9
  • 80
  • 159
0

As mentioned in comments to OP question, you have to generate Combination. The usual usecase is to take some subset of elements from a set. In this problem you take subset which represents elements taken from the first set and the rest will be taken from the second.

To implement combination I recommend a for loop counting from 0 to 2^n (where n is number of elements in one array). Then take this number and represent it in binary. Now each 0 or 1 in binary representation says from which set should be given number (and second set will be exact opposite).

I guess you have this as a homework or mental excercise so code is not included :]

Josh Crozier
  • 233,099
  • 56
  • 391
  • 304
  • I cant do like that, because the number of combinations for 3 values in one array is not 2^3, is more than that. – Nicolas Bontempo Aug 30 '15 at 00:01
  • @NicolasBontempo: 2^3 is not that big. So simply list those 8 cases and tell us what is missing. You said [1,2,3] and [1,3,2] are equal for you, so really there should be only those 8 cases. – flaschenpost Aug 30 '15 at 07:29
  • @flaschenpost sorry, you are right. Is only 1 more than 2^3. [123][567] [125][367] [126][537] [127][563] [135][267] [136][267] [137][256] [156][237] [157][236] [167][235] – Nicolas Bontempo Aug 30 '15 at 18:02
  • @NicolasBontempo you are right, 000 - 111 is wrong, so Vaclav Blazej is wrong. You take 3 of 6 from the whole set [1 2 3 5 6 7], that defines the operation. – flaschenpost Aug 30 '15 at 20:00
  • @flaschenpost You describe operation with equal solution ;) – Václav Blažej Aug 30 '15 at 20:04
  • @VáclavBlažej but 2^3 is not the same as 3 out of 6 = 9, or I'm living in a different universe. ;-) The difference is, that not only (from set 1) or (from set 2) counts, but which element of set1 or set2 – flaschenpost Aug 30 '15 at 20:18
  • @flaschenpost You are right. I supposed that elements from set1 must be swapped with elements from set2 which are on the same position - which seemed from to be a case from OP example – Václav Blažej Aug 31 '15 at 11:30
0

Your task is equal to list all 3-element subsets of your 6-element set. Since the order inside the 3-Element-set does not matter, you should define an order, like 'the smaller number comes first'.

Then the algorithm gets obvious: list = [1 2 3 5 6 7]

EDIT: Set1 should always be the set with number 1 in it, to avoid symmetrical identical solutions.

For all the numbers i from 2 to 5 for all the numbers j from i+1 to 5 Set1 = {list[1], list[i], list[j]} Set2 = "the other numbers"

This should give right your ordered list from your 9-element comment.

These are nested loops, obviously.

flaschenpost
  • 2,205
  • 1
  • 14
  • 29
  • This will give me the answer of sets1 [123] [235] [356] [567] and after that this will give me a error for index out of bounds. Because with i = 5 j will be equal 6 and k equal 7 (out of bound). – Nicolas Bontempo Aug 30 '15 at 20:30
  • the index problem I have fixed, symmetrical solutions avoided. But you should really try to see a nested loop if you need it. I get now 123, 125, 126, 127, 135, 136, 137, 156, 157, 167 , so 4+3+2+1 = 10 solutions – flaschenpost Aug 30 '15 at 20:46