java - 如何在 Java 中对子集进行排序

Question

亲爱的 friend 们，我有一个作业，我几乎解决了。但我最近遇到了一个大问题，我两天都找不到解决办法。如果您能帮助我，我将非常感激!

所以，假设用户输入了 5 (N) 我立即创建此序列以从中获取子集: {1,2,3,4,5}

如果 N = 4，则序列如下:{1, 2, 3, 4}等等

下面的代码生成子集的所有变体:

public static int[] genarator(int N)
{
    int[] generator = new int[(int) Math.pow(2, N)];
    int[] binDigit = new int[(int) Math.pow(2, N)];

    for (int i = 0; i < Math.pow(2, N); i++)
        generator[i] = (i >> 1) ^ i; // Right Shifting

    for (int i = 0; i < Math.pow(2, N); i++)
    {
        int one = 1;
        binDigit[i] = 0;
        while (generator[i] > 0)
        {
            binDigit[i] += (generator[i] % 2) * one;
            generator[i] /= 2;
            one = one * 10;
        }
    }

    return binDigit;
}

返回结果的方式如下所示(如果:N = 4 {1, 2, 3, 4})如下所示:

1 
1 2 
2 
2 3 
1 2 3 
1 3 
3 
3 4 
1 3 4 
1 2 3 4 
2 3 4 
2 4 
1 2 4 
1 4 
4 

但是我的讲师希望我的程序按以下顺序返回结果:

1
2
3
4
1 2
1 3
1 4
2 3
2 4
3 4
1 2 3
1 2 4
1 3 4
2 3 4
1 2 3 4

我现在使用TreeSet<Long>和parseLong所以我可以得到真实的结果，直到 1 <= N <= 9。但是每当用户输入 10 或更高的 N 时，它就会变得疯狂。

回顾一下，我的问题是我如何存储从int[] genarator(int N)获得的那些数字并按照我的讲师要求显示它们？

生成器如何工作以及如何获取顺序错误的数字？代码如下:

int N = read.nextInt();

        int[] sequence = new int[N];
        for (int i = 0; i < N; i++)
            sequence[i] = i + 1;

        int[] tempArray = new int[(int) Math.pow(2, N)];
        tempArray = genarator(N);

        for (int i = 1; i < Math.pow(2, N); i++)
        {
            for (int j = 0; j < N; j++)
            {
                if (tempArray[i] % 10 == 1)
                {
                    System.out.print(sequence[j] + " ");
                }
                tempArray[i] /= 10;
            }
            System.out.println();
        }

感谢您的检查，对于这个太长的问题我真的很抱歉。但我无法用简短的解释说清楚。

Answer 1

您可以做的是创建一个可以与其他集合进行比较的集合抽象。请参阅 Comparators 上的 Java 教程。

    //don't call this Set as there is already a Java Set 
    //interface that youdon't want to confuse yourself with   
    public class MySet implements Comparable<MySet>{

        int[] backingArray;

        public MySet(int n) {
           //initialize the Set
           this.backingArray = generator(n);
        }

        public static Int[] generator(int n) {
            //..whatever you do to generate your results
        }

        @Override
        public int compareTo(MySet otherSet) {
           //define how sets are compared (e.g what your professor is asking.  
           //In your example, if one set is shorter than another, 
           //it is considered 'smaller')
        }

    }

Set<MySet> allSets = ....;

并简单地调用Collections.sort(allSets);