java - 在Java深度生成列表n层的所有组合

coder 2024-04-01 原文

我正在使用以下代码来生成大小为s的组合的列表:

public static <T extends Comparable<? super T>> List<List<T>> combinations(List<T> items, int size) {
        if (size == 1) {
            List<List<T>> result = new ArrayList<>();
            for (T item : items) {
                result.add(Collections.singletonList(item));
            }
            return result ;
        }
        List<List<T>> result = new ArrayList<>();
        for (int i=0; i <= items.size() - size; i++) {
            T firstItem = items.get(i);
            List<List<T>> additionalItems = combinations(items.subList(i+1, items.size()), size-1) ;
            for (List<T> additional : additionalItems) {
                List<T> combination = new ArrayList<>();
                combination.add(firstItem);
                combination.addAll(additional);
                result.add(combination);
            }
        }
        return result ;
}

给定一个列表，其值1, 2 and 3的大小为2:

List<Integer> items = new ArrayList<Integer>();
items.add(1);
items.add(2);
items.add(3);

combinations(items, 2)

这将产生以下组合:

[1, 2]
[1, 3]
[2, 3]

我正在尝试获取此输出并生成第3个列表，其中以前输出的三行中的每行现在都与其他行合并在一起-仅在此时间顺序上敏感，并且深至'd'级别。我期望结果类似于以下输出:

1级深:

[1, 2]
[1, 3]
[2, 3]

深入2级:

[1, 2], [1, 3]
[1, 2], [2, 3]
[1, 3], [2, 3]
[1, 3], [1, 2]
[2, 3], [1, 2]
[2, 3], [1, 3]

深入3级:

[[1, 2], [1, 2], [1, 3]]
[[1, 2], [1, 2], [2, 3]]
[[1, 2], [1, 3], [1, 2]]
[[1, 2], [1, 3], [1, 3]]
[[1, 2], [1, 3], [2, 3]]
[[1, 2], [2, 3], [1, 2]]
[[1, 2], [2, 3], [1, 3]]
[[1, 2], [2, 3], [2, 3]]
[[1, 3], [1, 2], [1, 2]]
[[1, 3], [1, 2], [1, 3]]
[[1, 3], [1, 2], [2, 3]]
[[1, 3], [1, 3], [1, 2]]
[[1, 3], [1, 3], [2, 3]]
[[1, 3], [2, 3], [1, 2]]
[[1, 3], [2, 3], [1, 3]]
[[1, 3], [2, 3], [2, 3]]
[[2, 3], [1, 2], [1, 2]]
[[2, 3], [1, 2], [1, 3]]
[[2, 3], [1, 2], [2, 3]]
[[2, 3], [1, 3], [1, 2]]
[[2, 3], [1, 3], [1, 3]]
[[2, 3], [1, 3], [2, 3]]
[[2, 3], [2, 3], [1, 2]]
[[2, 3], [2, 3], [1, 3]]

深入4级:

[[1, 2], [1, 2], [1, 2], [1, 3]]
[[1, 2], [1, 2], [1, 2], [2, 3]]
[[1, 2], [1, 2], [1, 3], [1, 2]]
[[1, 2], [1, 2], [1, 3], [1, 3]]
[[1, 2], [1, 2], [1, 3], [2, 3]]
[[1, 2], [1, 2], [2, 3], [1, 2]]
[[1, 2], [1, 2], [2, 3], [1, 3]]
[[1, 2], [1, 2], [2, 3], [2, 3]]
[[1, 2], [1, 3], [1, 2], [1, 2]]
[[1, 2], [1, 3], [1, 2], [1, 3]]
[[1, 2], [1, 3], [1, 2], [2, 3]]
[[1, 2], [1, 3], [1, 3], [1, 2]]
[[1, 2], [1, 3], [1, 3], [1, 3]]
[[1, 2], [1, 3], [1, 3], [2, 3]]
[[1, 2], [1, 3], [2, 3], [1, 2]]
[[1, 2], [1, 3], [2, 3], [1, 3]]
[[1, 2], [1, 3], [2, 3], [2, 3]]
[[1, 2], [2, 3], [1, 2], [1, 2]]
[[1, 2], [2, 3], [1, 2], [1, 3]]
[[1, 2], [2, 3], [1, 2], [2, 3]]
[[1, 2], [2, 3], [1, 3], [1, 2]]
[[1, 2], [2, 3], [1, 3], [1, 3]]
[[1, 2], [2, 3], [1, 3], [2, 3]]
[[1, 2], [2, 3], [2, 3], [1, 2]]
[[1, 2], [2, 3], [2, 3], [1, 3]]
[[1, 2], [2, 3], [2, 3], [2, 3]]
[[1, 3], [1, 2], [1, 2], [1, 2]]
[[1, 3], [1, 2], [1, 2], [1, 3]]
[[1, 3], [1, 2], [1, 2], [2, 3]]
[[1, 3], [1, 2], [1, 3], [1, 2]]
[[1, 3], [1, 2], [1, 3], [1, 3]]
[[1, 3], [1, 2], [1, 3], [2, 3]]
[[1, 3], [1, 2], [2, 3], [1, 2]]
[[1, 3], [1, 2], [2, 3], [1, 3]]
[[1, 3], [1, 2], [2, 3], [2, 3]]
[[1, 3], [1, 3], [1, 2], [1, 2]]
[[1, 3], [1, 3], [1, 2], [1, 3]]
[[1, 3], [1, 3], [1, 2], [2, 3]]
[[1, 3], [1, 3], [1, 3], [1, 2]]
[[1, 3], [1, 3], [1, 3], [2, 3]]
[[1, 3], [1, 3], [2, 3], [1, 2]]
[[1, 3], [1, 3], [2, 3], [1, 3]]
[[1, 3], [1, 3], [2, 3], [2, 3]]
[[1, 3], [2, 3], [1, 2], [1, 2]]
[[1, 3], [2, 3], [1, 2], [1, 3]]
[[1, 3], [2, 3], [1, 2], [2, 3]]
[[1, 3], [2, 3], [1, 3], [1, 2]]
[[1, 3], [2, 3], [1, 3], [1, 3]]
[[1, 3], [2, 3], [1, 3], [2, 3]]
[[1, 3], [2, 3], [2, 3], [1, 2]]
[[1, 3], [2, 3], [2, 3], [1, 3]]
[[1, 3], [2, 3], [2, 3], [2, 3]]
[[2, 3], [1, 2], [1, 2], [1, 2]]
[[2, 3], [1, 2], [1, 2], [1, 3]]
[[2, 3], [1, 2], [1, 2], [2, 3]]
[[2, 3], [1, 2], [1, 3], [1, 2]]
[[2, 3], [1, 2], [1, 3], [1, 3]]
[[2, 3], [1, 2], [1, 3], [2, 3]]
[[2, 3], [1, 2], [2, 3], [1, 2]]
[[2, 3], [1, 2], [2, 3], [1, 3]]
[[2, 3], [1, 2], [2, 3], [2, 3]]
[[2, 3], [1, 3], [1, 2], [1, 2]]
[[2, 3], [1, 3], [1, 2], [1, 3]]
[[2, 3], [1, 3], [1, 2], [2, 3]]
[[2, 3], [1, 3], [1, 3], [1, 2]]
[[2, 3], [1, 3], [1, 3], [1, 3]]
[[2, 3], [1, 3], [1, 3], [2, 3]]
[[2, 3], [1, 3], [2, 3], [1, 2]]
[[2, 3], [1, 3], [2, 3], [1, 3]]
[[2, 3], [1, 3], [2, 3], [2, 3]]
[[2, 3], [2, 3], [1, 2], [1, 2]]
[[2, 3], [2, 3], [1, 2], [1, 3]]
[[2, 3], [2, 3], [1, 2], [2, 3]]
[[2, 3], [2, 3], [1, 3], [1, 2]]
[[2, 3], [2, 3], [1, 3], [1, 3]]
[[2, 3], [2, 3], [1, 3], [2, 3]]
[[2, 3], [2, 3], [2, 3], [1, 2]]
[[2, 3], [2, 3], [2, 3], [1, 3]]

请注意，在2个级别的深度，组合[1, 2], [1, 2]不会生成，因为在该组合之间，之前或之后没有一组不同的数字。但是，由于在两对[1, 2], [1, 3], [1, 2]之间存在[1, 3]组合，因此在3个级别的深度我们会生成[1, 2]组合。

类似地，在4层深处，我们生成序列[1, 2], [1, 3], [1, 2], [1, 2]，它与序列[1, 2], [1, 3], [1, 2]不同，因为[1, 2]之后还有另外的[1, 2], [1, 3], [1, 2]序列。我们不会在4层深度处生成[1, 2], [1, 2], [1, 2], [1, 2]序列，因为此组合基本上等效于[1, 2]，因为在[1, 2]组合之前，之后或之后没有新的数字集。

简而言之，我如何合并一个数字列表的列表-最多可以达到任何数量的级别(仅以1-4为例)，但是这次结果是顺序敏感的(因此[1, 2], [1, 3]不等于[1, 3], [1, 2])？结果可能存储在List<List<List<Integer>>>中。

我在StackOverflow上进行了搜索，并看到了几个生成组合的线程(例如this one和this one)，但没有解决上面概述的确切情况。

谢谢

最佳答案

我相信我做了你想要的。代码分为四个单独的方法(如果必须为1，则没有任何区别):

public static <T extends Comparable<? super T>> List<List<List<T>>> level(List<List<T>> items, int level) {
    List<List<List<T>>> result = new ArrayList<>();
    if(level == 1) {
        for(List<T> item : items) {
            result.add(Collections.singletonList(item));
        }
        return result;
    }

    for(int i = 0; i < level; i++) {
        if(i == 0) {
            for(List<T> item : items)
                result.add(Collections.singletonList(item));
            continue;
        }

        List<List<List<T>>> newResult = new ArrayList<>();
        for(List<List<T>> item : result) {
            List<List<List<T>>> combined = new ArrayList<>();
            List<T> first = item.get(0);
            for(int j = 0; j < items.size(); j++) {
                List<List<T>> current = new ArrayList<>();
                List<T> it = items.get(j);
                current.addAll(item);
                current.add(it);

                combined.add(current);
            }

            newResult.addAll(combined);
        }

        result = newResult;
    }

    clean(result);
    return result;
}

这就是大多数算法的作用。首先，就像您提供的函数一样，它检查级别是否为1，在这种情况下，您可以像给定方法一样返回列表列表。之后，我们遍历了所有级别。我们首先检查当前级别是否为1，在这种情况下，它将执行与方法调用级别1相同的操作。接下来，我们创建一个名为newResult的新列表。此变量基本上是result的临时值，可防止并发修改异常。然后，我们遍历result中已经存在的每个值。我们根据已有的值创建一些新值，并将它们添加到combined中。然后，我们将combined添加到newResult中，该算法基本上结束了。现在，当所有值都相同时(例如[1, 2], [1, 2], [1, 2], [1, 2])，这些循环将不会计入。因此，我们调用clean方法来删除这些情况。

public static <T extends Comparable<? super T>> void clean(List<List<List<T>>> list) {
    List<List<List<T>>> removals = new ArrayList<>();
    for(List<List<T>> item : list) {
        if(!check(item))
            removals.add(item);
    }
    for(List<List<T>> item : removals) {
        list.remove(item);
    }
}

此方法贯穿给定列表内的所有内容，并在元素上运行check方法。对该方法进行了进一步的说明。如果该元素无效，则将其标记为删除，并在下一个循环中删除。

public static <T extends Comparable<? super T>> boolean check(List<List<T>> list) {
    if(list.size() < 2) return true;

    for(int i = 1; i < list.size(); i++) {
        List<T> previous = list.get(i-1);
        List<T> item = list.get(i);

        if(notEqual(previous, item)){
            return true;
        }
    }

    return false;
}

该循环通过将一个列表与另一个列表进行比较，直到找到两个不同的列表，来检查给定列表是否有效。发生这种情况时，该列表有效，并返回true。如果不是，它将永远不会返回，将跳出循环并返回false。

public static <T extends Comparable<? super T>> boolean notEqual(List<T> a, List<T> b) {
    for(int i = 0; i < Math.min(a.size(), b.size()); i++) {
        T ao = a.get(i);
        T bo = b.get(i);

        if(ao.compareTo(bo) != 0)
            return true;
    }

    return false;
}

此方法采用两个输入列表，并检查其中的元素是否不相等。它遍历两个列表，使元素处于相同的索引，并将它们相互比较。如果它们不相等，则返回true，否则，它完成循环并返回false。

请注意，这仅是概念证明，而不是最终版本。它的很多方面都可以肯定地加以改进，但这是您所要求的工作版本。

Link to working version on jDoodle

如果您对它的任何方面有任何疑问，或想要澄清任何内容，请随时提出!

编辑:
我已经修改了算法，以结合您的要求。这是新的代码:

public static <T extends Comparable<? super T>> List<List<List<T>>> level(List<List<T>> items, int minLevel, int maxLevel) {
    List<List<List<T>>> result = new ArrayList<>();

    for(int i = minLevel; i < maxLevel+1; i++) {
        result.addAll(level(items, i));
    }

    return result;
}

这是重载的方法，可让您指定所需的级别范围。给定最小和最大级别，它将返回一个新列表，其中包含该范围内(包括端值)的所有级别。正如您所说，作为一个简单的循环，它相对来说比较琐碎。

public static <T extends Comparable<? super T>> List<List<List<T>>> level(List<List<T>> items, int level) {
    List<List<List<T>>> result = new ArrayList<>();
    if(level == 1) {
        for(List<T> item : items) {
            result.add(Collections.singletonList(item));
        }
        return result;
    }

    for(int i = 0; i < level; i++) {
        if(i == 0) {
            for(List<T> item : items)
                result.add(Collections.singletonList(item));
            continue;
        }

        List<List<List<T>>> newResult = new ArrayList<>();
        for(List<List<T>> item : result) {
            if(item.size() < i)
                continue;

            List<List<List<T>>> combined = new ArrayList<>();
            List<T> first = item.get(0);
            for(int j = 0; j < items.size(); j++) {
                List<List<T>> current = new ArrayList<>();
                List<T> it = items.get(j);
                current.addAll(item);
                current.add(it);

                combined.add(current);
            }

            newResult.addAll(combined);
        }

        result = newResult;
    }

    List<List<List<T>>> removals = new ArrayList<>();
    for(List<List<T>> item : result) {
        if(!check(item))
            removals.add(item);
    }
    for(List<List<T>> item : removals) {
        result.remove(item);
    }

    return result;
}

这是修改后的方法。我删除了clean方法，并将其放在level方法内，因为它只被调用了一次。我认为实际上是不可能的，至少使用当前代码在算法期间运行该clean方法，因为在这个时间点上，它的工作方式是针对给定级别生成所有可能的组合，然后转到下一个。如果删除了相同的组合，则在下一级别，将不会添加这些组合。

这是一个例子:
说我有[1, 2], [1, 3], [2, 3]。如果我升到第二级，我将在您的问题中指定组合。很明显吧？好吧，如果我随后仅使用第2级的结果进入第3级，则我会错过所有包含[1, 2], [1, 2] [...]的组合，因为这不在给定列表中。这是算法的问题，可以肯定地加以改进。

我计划进一步对其进行重构，以使其在算法中进行检查，但是这样做可能会花费我很多时间。

New working version in jDoodle

编辑2:
实际上，将clean方法并入算法实际上比我最初想象的要简单得多。这是带有一些注释的新代码:

public static <T extends Comparable<? super T>> List<List<List<T>>> level(List<List<T>> items, int level) {
    List<List<List<T>>> result = new ArrayList<>();
    for(int i = 0; i < level; i++) {
        if(i == 0) { // If level is 0, we can just add the items as singleton lists to the result
            for(List<T> item : items)
                result.add(Collections.singletonList(item));
            continue;
        }

        List<List<List<T>>> newResult = new ArrayList<>(); // Temporary items that will be added
        for(List<List<T>> item : result) {
            if(item.size() < i) // Make sure we are manipulating items that are on the previous level
                continue;

            List<List<List<T>>> combined = new ArrayList<>(); // The temporary values for this specific item
            for(int j = 0; j < items.size(); j++) {
                List<List<T>> current = new ArrayList<>(); // The current list with the value
                current.addAll(item); // Add the current items from result to the list
                current.add(items.get(j)); // Add the current item from items to the list

                if (i == level-1 && !check(current)) { // If this is the last level, and the current list shouldn't be added, skip adding
                    continue;
                }

                combined.add(current); // Add the current list to the combined values
            }

            newResult.addAll(combined); // Add all of the lists in combined to the new result
        }

        result = newResult; // Make result equal to the new result
    }

    return result;
}

现在要做的是，在将新组合添加到列表时，它首先检查当前级别是否为最终级别。如果是这样，它将实际检查该列表，如果无效，它将跳过实际添加的列表。

我再次计划以一种更加智能的格式完全重写该算法，但是此代码现在完全可以使用。

Working version on jDoodle

关于java - 在Java深度生成列表n层的所有组合，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/55487095/

java List code lt algorithm math combinations combinatorics

有关java - 在Java深度生成列表n层的所有组合的更多相关文章

ruby - 使用 RubyZip 生成 ZIP 文件时设置压缩级别 - 2
我有一个Ruby程序，它使用rubyzip压缩XML文件的目录树。gem。我的问题是文件开始变得很重，我想提高压缩级别，因为压缩时间不是问题。我在rubyzipdocumentation中找不到一种为创建的ZIP文件指定压缩级别的方法。有人知道如何更改此设置吗？是否有另一个允许指定压缩级别的Ruby库？最佳答案这是我通过查看rubyzip内部创建的代码。level=Zlib::BEST_COMPRESSIONZip::ZipOutputStream.open(zip_file)do|zip|Dir.glob("**/*")d
ruby - 如何以所有可能的方式将字符串拆分为长度最多为 3 的连续子字符串？ - 2
我试图获取一个长度在1到10之间的字符串，并输出将字符串分解为大小为1、2或3的连续子字符串的所有可能方式。例如:输入:123456将整数分割成单个字符，然后继续查找组合。该代码将返回以下所有数组。[1,2,3,4,5,6][12,3,4,5,6][1,23,4,5,6][1,2,34,5,6][1,2,3,45,6][1,2,3,4,56][12,34,5,6][12,3,45,6][12,3,4,56][1,23,45,6][1,2,34,56][1,23,4,56][12,34,56][123,4,5,6][1,234,5,6][1,2,345,6][1,2,3,456][123
ruby - 在 jRuby 中使用 'fork' 生成进程的替代方案？ - 2
在MRIRuby中我可以这样做:deftransferinternal_server=self.init_serverpid=forkdointernal_server.runend#Maketheserverprocessrunindependently.Process.detach(pid)internal_client=self.init_client#Dootherstuffwithconnectingtointernal_server...internal_client.post('somedata')ensure#KillserverProcess.kill('KILL',
ruby - 如何使用 Ruby aws/s3 Gem 生成安全 URL 以从 s3 下载文件 - 2
我正在编写一个小脚本来定位aws存储桶中的特定文件，并创建一个临时验证的url以发送给同事。(理想情况下，这将创建类似于在控制台上右键单击存储桶中的文件并复制链接地址的结果)。我研究过回形针，它似乎不符合这个标准，但我可能只是不知道它的全部功能。我尝试了以下方法:defauthenticated_url(file_name,bucket)AWS::S3::S3Object.url_for(file_name,bucket,:secure=>true,:expires=>20*60)end产生这种类型的结果:...-1.amazonaws.com/file_path/file.zip.A
ruby - RVM 使用列表[0] - 2
是否有类似“RVMuse1”或“RVMuselist[0]”之类的内容而不是键入整个版本号。在任何时候，我们都会看到一个可能包含5个或更多ruby的列表，我们可以轻松地键入一个数字而不是X.X.X。这也有助于rvmgemset。最佳答案这在RVM2.0中是可能的=>https://docs.google.com/document/d/1xW9GeEpLOWPcddDg_hOPvK4oeLxJmU3Q5FiCNT7nTAc/edit?usp=sharing-知道链接的任何人都可以发表评论
java - 等价于 Java 中的 Ruby Hash - 2
我真的很习惯使用Ruby编写以下代码:my_hash={}my_hash['test']=1Java中对应的数据结构是什么？最佳答案 HashMapmap=newHashMap();map.put("test",1);我假设？关于java-等价于Java中的RubyHash，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/22737685/
ruby-on-rails - 跳过状态机方法的所有验证 - 2
当我的预订模型通过rake任务在状态机上转换时，我试图找出如何跳过对ActiveRecord对象的特定实例的验证。我想在reservation.close时跳过所有验证!叫做。希望调用reservation.close!(:validate=>false)之类的东西。仅供引用，我们正在使用https://github.com/pluginaweek/state_machine用于状态机。这是我的预订模型的示例。classReservation["requested","negotiating","approved"])}state_machine:initial=>'requested
ruby - Nokogiri 剥离所有属性 - 2
我有这个html标记:我想得到这个:我如何使用Nokogiri做到这一点？最佳答案 require'nokogiri'doc=Nokogiri::HTML('')您可以通过xpath删除所有属性:doc.xpath('//@*').remove或者，如果您需要做一些更复杂的事情，有时使用以下方法遍历所有元素会更容易:doc.traversedo|node|node.keys.eachdo|attribute|node.deleteattributeendend 关于ruby-Nokog
ruby - 获取模块中定义的所有常量的值 - 2
我想获取模块中定义的所有常量的值:moduleLettersA='apple'.freezeB='boy'.freezeendconstants给了我常量的名字:Letters.constants(false)#=>[:A,:B]如何获取它们的值的数组，即["apple","boy"]？最佳答案为了做到这一点，请使用mapLetters.constants(false).map&Letters.method(:const_get)这将返回["a","b"]第二种方式:Letters.constants(false).map{|c
ruby-on-rails - Ruby on Rails - 为文本区域和图片生成列 - 2
我是Rails的新手，所以请原谅简单的问题。我正在为一家公司创建一个网站。那家公司想在网站上展示它的客户。我想让客户自己管理这个。我正在为“客户”生成一个表格，我想要的三列是:公司名称、公司描述和Logo。对于名称，我使用的是name:string但不确定如何在脚本/生成脚手架终端命令中最好地创建描述列(因为我打算将其设置为文本区域)和图片。我怀疑描述(我想成为一个文本区域)应该仍然是描述:字符串，然后以实际形式进行调整。不确定如何处理图片字段。那么……说来话长:我在脚手架命令中输入什么来生成描述和图片列？最佳答案对于“文本”数

java - 在Java深度生成列表n层的所有组合

有关java - 在Java深度生成列表n层的所有组合的更多相关文章

随机推荐