找到向量集的最小元素

Question

我有一组向量，我需要用java编写算法，找到这个集合的最小元素。问题是，有些元素是无与伦比的。例如minset{（1,4,6），（3,2,5），（2,3,4），（5,4,6)} = {(1,4,6），（3,2,5），（2,3,4）}。对于最小元素集“minset”，以下内容成立：原始集的每个向量要么在“minset”中，要么在“minset”中

Answer 1

我在文章中找到了解决问题的方法http://repository.cmu.edu/cgi/viewcontent.cgi?article=2758

Answer 2

伪代码：

foreach inputVector in vectors
    foreach minVector in minSet
        if (all components of inputVector <= components of minVector
            delete minVector
        elseif (all components of inputVector >= components of minVector)       
            skip to next inputVector
    if inputVector made it through the entire minSet, then add it to minSet

Answer 3

我创建了一个可运行的示例。它使用Java的内置Arrays.sort（）和一个比较器来比较大小为L的两个向量。如果您更喜欢在数组上使用List数据结构，您可以使用Collections.sort做类似的事情。

来自 Java API 规范：

This algorithm offers guaranteed n*log(n) performance.

import java.util.*;
import java.lang.*;

class Main
{
    public static void main (String[] args) throws java.lang.Exception
    {
        final int L = 3;

        int[][] vectors = {
            {1, 4, 6},
            {3, 2, 5},
            {2, 3, 4},
            {5, 4, 6},
            {7, 7, 7},
            {3, 3, 5},
            {8, 8, 8},
        };

        Comparator<int[]> cmp = new Comparator<int[]>() {
            public int compare(int[] v1, int[] v2) {
                int cmp0 = Integer.signum(v1[0] - v2[0]);
                for (int i = 0; i < L; i++) {
                int cmp1 = Integer.signum(v1[i] - v2[i]);
                    if (cmp1 != 0) {
                        if (cmp1 != cmp0) {
                            return 0;
                        }
                        cmp0 = cmp1;
                    }
                }
                return cmp0;
            }
        };

        Arrays.sort(vectors, cmp);

        System.out.println("minset:");
        int i = 0;
        int[] vPref = vectors[0];
        while (cmp.compare(vectors[i], vPref) == 0) {
            for (int x : vectors[i]){
                System.out.print(x + ", ");
            }
            System.out.println();
            vPref = vectors[i];
            i++;
        }
    }
}