LinkedHashSet 和 subList，获取集合的 n

Question

我正在尝试做一个数学作业，它是找到集合 {1,2,..,n} 的一个子集，其中 n 是代码中给出的数字，我无法用子列表完成它所以我需要得到你的数学编程方面的帮助。

例如 n = 2:

[12]
[1][2]

它有 2 个元素。

例如 n = 3:

[1][2][3]
[12][3]
[13][2]
[23][1]
[123]

它有 5 个元素。

它有五个元素。

对于 n = 4:

[1][2][3][4]
[12][3][4]
[13][2][4]
[14][2][3]
[23][1][4]
[24][1][3]
[34][1][2]
[12][34]
[13][24]
[14][23]
[123][4]
[124][3]
[134][2]
[234][1]
[1234]

它有 15 个元素。

您对如何完成它有任何想法吗？

我已经尝试了很多在循环中使用 LinkedHashSet 和子列表的可能性，但是我在 2 小时多的时间里都不知道如何完成它，输出是这样的。

Java 中是否有任何库可以获取此输出？我会通过手动方式做到这一点，但必须有不同的方式。

import org.paukov.combinatorics.*;
import org.paukov.combinatorics.util.ComplexCombinationGenerator;

public class Main {
    public static void main(String args[]){

           // create a vector (A, B, B, C)
           ICombinatoricsVector<String> vector = Factory.createVector(new String[] { "1", "2", "3"});

           // Create a complex-combination generator
           Generator<ICombinatoricsVector<String>> gen = new ComplexCombinationGenerator<String>(vector, 1);
           Generator<ICombinatoricsVector<String>> gen2 = new ComplexCombinationGenerator<String>(vector, 2);
           Generator<ICombinatoricsVector<String>> gen3 = new ComplexCombinationGenerator<String>(vector, 3);
           // Iterate the combinations
           for (ICombinatoricsVector<ICombinatoricsVector<String>> comb : gen) {
                  System.out.println(ComplexCombinationGenerator.convert2String(comb) + " - " + comb);
               }
           for (ICombinatoricsVector<ICombinatoricsVector<String>> comb : gen2) {
                  System.out.println(ComplexCombinationGenerator.convert2String(comb) + " - " + comb);
               }
           for (ICombinatoricsVector<ICombinatoricsVector<String>> comb : gen3) {
                  System.out.println(ComplexCombinationGenerator.convert2String(comb) + " - " + comb);
               }

    }


}






([1, 2, 3]) - CombinatoricsVector=([CombinatoricsVector=([1, 2, 3], size=3)], size=1)
([1],[2, 3]) - CombinatoricsVector=([CombinatoricsVector=([1], size=1), CombinatoricsVector=([2, 3], size=2)], size=2)
([2, 3],[1]) - CombinatoricsVector=([CombinatoricsVector=([2, 3], size=2), CombinatoricsVector=([1], size=1)], size=2)
([2],[1, 3]) - CombinatoricsVector=([CombinatoricsVector=([2], size=1), CombinatoricsVector=([1, 3], size=2)], size=2)
([1, 3],[2]) - CombinatoricsVector=([CombinatoricsVector=([1, 3], size=2), CombinatoricsVector=([2], size=1)], size=2)
([1, 2],[3]) - CombinatoricsVector=([CombinatoricsVector=([1, 2], size=2), CombinatoricsVector=([3], size=1)], size=2)
([3],[1, 2]) - CombinatoricsVector=([CombinatoricsVector=([3], size=1), CombinatoricsVector=([1, 2], size=2)], size=2)
([1],[2],[3]) - CombinatoricsVector=([CombinatoricsVector=([1], size=1), CombinatoricsVector=([2], size=1), CombinatoricsVector=([3], size=1)], size=3)
([1],[3],[2]) - CombinatoricsVector=([CombinatoricsVector=([1], size=1), CombinatoricsVector=([3], size=1), CombinatoricsVector=([2], size=1)], size=3)
([3],[1],[2]) - CombinatoricsVector=([CombinatoricsVector=([3], size=1), CombinatoricsVector=([1], size=1), CombinatoricsVector=([2], size=1)], size=3)
([3],[2],[1]) - CombinatoricsVector=([CombinatoricsVector=([3], size=1), CombinatoricsVector=([2], size=1), CombinatoricsVector=([1], size=1)], size=3)
([2],[3],[1]) - CombinatoricsVector=([CombinatoricsVector=([2], size=1), CombinatoricsVector=([3], size=1), CombinatoricsVector=([1], size=1)], size=3)
([2],[1],[3]) - CombinatoricsVector=([CombinatoricsVector=([2], size=1), CombinatoricsVector=([1], size=1), CombinatoricsVector=([3], size=1)], size=3)

Answer 1

这个问题可以使用动态规划来解决，其中您将一个复杂的问题分解成子集。

我认为这个 post 可能有用： Combaintions of set of numbers

Answer 2

这是组合数学。查看有关您需要了解的结构的更多信息，即 permutation without repetition, also called a combination.

您可能对 combinatoricslib 感兴趣，它是 Google 代码的 Java 库，可用于您的程序。

你也可以尝试不用库来解决。那应该不会太难。我认为你需要使用递归。

我测试了列表分区：

import org.paukov.combinatorics.*;
import org.paukov.combinatorics.util.ComplexCombinationGenerator;

public class Main {

    public static void main(String args[]){

        // create a vector (1, 2, 3, 4)
        ICombinatoricsVector<String> vector = Factory.createVector(new String[] { "1", "2", "3", "4" });

        // Create a complex-combination generator
        Generator<ICombinatoricsVector<String>> gen = new ComplexCombinationGenerator<String>(vector, 2);

        // Iterate the combinations
        for (ICombinatoricsVector<ICombinatoricsVector<String>> comb : gen) {
            System.out.println(ComplexCombinationGenerator.convert2String(comb) + " - " + comb);
        }
    }
}

结果是

([1],[2, 3, 4]) - CombinatoricsVector=([CombinatoricsVector=([1], size=1), CombinatoricsVector=([2, 3, 4], size=3)], size=2)
([2, 3, 4],[1]) - CombinatoricsVector=([CombinatoricsVector=([2, 3, 4], size=3), CombinatoricsVector=([1], size=1)], size=2)
([2],[1, 3, 4]) - CombinatoricsVector=([CombinatoricsVector=([2], size=1), CombinatoricsVector=([1, 3, 4], size=3)], size=2)
([1, 3, 4],[2]) - CombinatoricsVector=([CombinatoricsVector=([1, 3, 4], size=3), CombinatoricsVector=([2], size=1)], size=2)
([1, 2],[3, 4]) - CombinatoricsVector=([CombinatoricsVector=([1, 2], size=2), CombinatoricsVector=([3, 4], size=2)], size=2)
([3, 4],[1, 2]) - CombinatoricsVector=([CombinatoricsVector=([3, 4], size=2), CombinatoricsVector=([1, 2], size=2)], size=2)
([3],[1, 2, 4]) - CombinatoricsVector=([CombinatoricsVector=([3], size=1), CombinatoricsVector=([1, 2, 4], size=3)], size=2)
([1, 2, 4],[3]) - CombinatoricsVector=([CombinatoricsVector=([1, 2, 4], size=3), CombinatoricsVector=([3], size=1)], size=2)
([1, 3],[2, 4]) - CombinatoricsVector=([CombinatoricsVector=([1, 3], size=2), CombinatoricsVector=([2, 4], size=2)], size=2)
([2, 4],[1, 3]) - CombinatoricsVector=([CombinatoricsVector=([2, 4], size=2), CombinatoricsVector=([1, 3], size=2)], size=2)
([2, 3],[1, 4]) - CombinatoricsVector=([CombinatoricsVector=([2, 3], size=2), CombinatoricsVector=([1, 4], size=2)], size=2)
([1, 4],[2, 3]) - CombinatoricsVector=([CombinatoricsVector=([1, 4], size=2), CombinatoricsVector=([2, 3], size=2)], size=2)
([1, 2, 3],[4]) - CombinatoricsVector=([CombinatoricsVector=([1, 2, 3], size=3), CombinatoricsVector=([4], size=1)], size=2)
([4],[1, 2, 3]) - CombinatoricsVector=([CombinatoricsVector=([4], size=1), CombinatoricsVector=([1, 2, 3], size=3)], size=2)

我想这就是您要找的。虽然它需要一些调整（可能排序和添加初始列表元素，如 [1],[2],[3],[4]）。

LinkedHashSet 和 subList，获取集合的 n

LinkedHashSet and subList, getting n of collection

java

math

set

linkedhashset