java - 两个 vector 之间的排列

Question

我正在研究一些算法技术，但遇到了一个问题，我需要在两组之间进行排列。例如:

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

需要生成:

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

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

........

等等。

据此到目前为止我所做的 是在你们之间的一个 vector 中进行排列。

传递一个 vector [1,2,3]。生成答案:123132213231321312

基于下面的代码:

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

如何在这两个 vector 之间进行排列？

Answer 1

尽管您没有准确描述您要查找的内容，并尝试回答:看起来您只是在查找输入的所有 3 元素子集 (1,2,3, 5,6,7).每个子集是一个解的第一个 vector ，其余元素分别是另一个 vector 。

这是一个如何计算的例子，基于 ChoiceIterable我刚才写的实用类:

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

这个例子中的输出将是

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

如果这不是您一直在寻找的结果，您应该更清楚、更准确地描述预期结果是什么。

(例如是否

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

和

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

不同结果的计数由您决定，但您可以相应地过滤结果)