草庐IT

java - 查找列表所有可能拆分的算法

coder 2024-04-02 原文

我正在使用我创建的链表，其中包含一组数字作为数据。我需要找到一种方法来测试此列表的每个可能的两组分区，为此，我需要将列表分解为每个可能的两组组合。顺序并不重要，而且会有重复。 

For instance, for a list of numbers {1 4 3 1}, the possible splits are 

{1} and {4, 3, 1}
{4} and {1, 3, 1}
{3} and {1, 4, 1}
{1} and {1, 4, 3}
{1, 4} and {3, 1}
{1, 3} and {4, 1}
{1, 1} and {4, 3}

4 个数字的列表并不难，但随着列表变大，事情变得越来越复杂，而且我很难看出规律。谁能帮我找到一个算法？

编辑:

抱歉，我没看到问题。到目前为止，这是我尝试过的。我的循环结构是错误的。当我在尝试常规数组后弄清楚我在做什么时，我将扩展算法以适合我的链表。

public class TwoSubsets
{
    public static void main(String[] args)
    {
        int[] list = {1, 3, 5, 7, 8};
        int places = 1;

        int[] subsetA = new int[10];
        int[] subsetB = new int[10];


        for (int i = 0; i < list.length; i++)
        {
            subsetA[i] = list[i];       
            for (int current = 0; current < (5 - i ); current++)
            {
                subsetB[current] = list[places];        
                places++;

            }

            System.out.print("subsetA = ");
            for (int j = 0; j < subsetA.length; j++)
            {
                System.out.print(subsetA[j] + " ");
            }

            System.out.println();
            System.out.print("subsetB = ");
            for (int k = 0; k < subsetB.length; k++)
            {
                System.out.print(subsetB[k] + " ");
            }



        }
    }

}

最佳答案

因此，除了互补子集之外，您正在寻找给定集合的所有(适当的)子集。如果您的列表有 n 个元素，您将有 2^n 个子集。但是，由于您不想要空子集并且想要用 (B,A) 标识分区 (A,B)，因此您会得到 2^(n-1)-1 个分区。

要枚举它们，您可以使用 n 位二进制数来标识分区，其中位置 k 中的数字 0 表示列表的第 k 个元素在分区的第一组中，1 表示它在第二个。你想用它的互补来识别一个数字(与另一个交换一个集合)并且你想排除 0(空子集)。

所以你可以使用位运算。 XOR 运算符为您提供互补分割。所以像下面这样的东西应该起作用:

int m = (1<<n)-1; // where n is the number of elements, m=111111...11 in binary
for (int i=0;i<m-1;++i) {
    if (i>(m^i)) continue; // this was already considered with 0 and 1 exchanged
    // here the binary digits of i represent the partition
    for (int j=0;j<n;++j) {
       if ((1<<j) & i) {
          // the j-th element of the list goes into the second set of the partition
       } else {
          // the j-th element of the list goes into the first set of the partition
       }
    }
}

关于java - 查找列表所有可能拆分的算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/19892115/

java查找sectionintthealgorithm

有关java - 查找列表所有可能拆分的算法的更多相关文章

  1. 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

  2. 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-知道链接的任何人都可以发表评论

  3. ruby - 如何在 Ruby 中拆分参数字符串 Bash 样式？ - 2

    我正在为一个项目制作一个简单的shell，我希望像在Bash中一样解析参数字符串。foobar"helloworld"fooz应该变成:["foo","bar","helloworld","fooz"]等等。到目前为止，我一直在使用CSV::parse_line，将列分隔符设置为""和.compact输出。问题是我现在必须选择是要支持单引号还是双引号。CSV不支持超过一个分隔符。Python有一个名为shlex的模块:>>>shlex.split("Test'helloworld'foo")['Test','helloworld','foo']>>>shlex.split('Test"

  4. 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/

  5. 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

  6. 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

  7. ruby - 当使用::指定模块时，为什么 Ruby 不在更高范围内查找类？ - 2

    我刚刚被困在这个问题上一段时间了。以这个基地为例:moduleTopclassTestendmoduleFooendend稍后，我可以通过这样做在Foo中定义扩展Test的类:moduleTopmoduleFooclassSomeTest但是，如果我尝试通过使用::指定模块来最小化缩进:moduleTop::FooclassFailure这失败了:NameError:uninitializedconstantTop::Foo::Test这是一个错误，还是仅仅是Ruby解析变量名的方式的逻辑结果？ 最佳答案 Isthisabug,or

  8. 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

  9. ruby - 查找字符串中的内容类型(数字、日期、时间、字符串等) - 2

    我正在尝试解析一个CSV文件并使用SQL命令自动为其创建一个表。CSV中的第一行给出了列标题。但我需要推断每个列的类型。Ruby中是否有任何函数可以找到每个字段中内容的类型。例如，CSV行:"12012","Test","1233.22","12:21:22","10/10/2009"应该产生像这样的类型['integer','string','float','time','date']谢谢! 最佳答案 require'time'defto_something(str)if(num=Integer(str)rescueFloat(s

  10. java - 从 JRuby 调用 Java 类的问题 - 2

    我正在尝试使用boilerpipe来自JRuby。我看过guide从JRuby调用Java，并成功地将它与另一个Java包一起使用，但无法弄清楚为什么同样的东西不能用于boilerpipe。我正在尝试基本上从JRuby中执行与此Java等效的操作:URLurl=newURL("http://www.example.com/some-location/index.html");Stringtext=ArticleExtractor.INSTANCE.getText(url);在JRuby中试过这个:require'java'url=java.net.URL.new("http://www

随机推荐