算法找到一个列表的所有可能分割 [英] Algorithm to find all possible splits of a list

问题描述

我正在与我创建的，其中包含了一组数字作为数据的链接列表。我需要找到一个方法来测试这个名单的东西一切可能的两集的分区，而要做到这一点，我需要打破名单为每一个可能的两集组合。顺序并不重要，会出现重复。

 例如，对于数字{1 4 3 1}的名单，可能的分裂是

{1}和{4,3，1}
{4}和{1，3,1}
{3}和{1，4,1}
{1}和{1，4,3}
{1,4}和{3,1}
{1,3}和{4,1}
{1，1}和{4,3}
 

4号的名单并不难，但事情变得更加复杂，因为列表变大，而我无法看到的模式。谁能帮我找到一个算法呢？

编辑：

对不起，我没有看到这个问题。这是我试过至今。我的循环结构是错误的。当我找出我想定期阵列后我在做，我将扩展算法，以适应我的链接列表。

 公共类TwoSubsets
{
    公共静态无效的主要（字串[] args）
    {
        INT []列表= {1，3，5，7，8};
        INT地方= 1;

        INT [] subsetA =新INT [10];
        INT [] subsetB =新INT [10];


        的for（int i = 0; I＆LT; list.length;我++）
        {
            subsetA [i] =列表[我]
            为（中间体电流= 0;电流I;（5  - ⅰ）;电流++）
            {
                subsetB [当前] =列表[地方]
                地方++;

            }

            System.out.print（subsetA =）;
            对于（INT J = 0; J＆LT; subsetA.length; J ++）
            {
                System.out.print（subsetA [J]。+）;
            }

            的System.out.println（）;
            System.out.print（subsetB =）;
            对于（INT K = 0; K＆LT; subsetB.length; k ++）
            {
                System.out.print（subsetB [K] +）;
            }



        }
    }

}
 

解决方案

code：

 公共静态无效的主要（字串[] args）{
    对于（字符串元素：findSplits（名单））{
        的System.out.println（元）;
    }
}

静态的ArrayList＆LT;字符串＆GT; findSplits（ArrayList的＆LT;整数GT;集）{
    ArrayList的＆LT;字符串＆GT;输出=新的ArrayList（）;
    ArrayList的＆LT;整数GT;第一=新的ArrayList（），第二=新的ArrayList（）;
    串位串;
    INT位=（int）的Math.pow（2，set.size（））;
    而（bits--大于0）{
        比特串的String.Format =（％+ set.size（）+的，Integer.toBinaryString（比特））代替（''，'0'）。
        的for（int i = 0; I＆LT; set.size（）;我++）{
            如果（bitString.substring（I，I + 1）的.equals（0））{
                first.add（set.get（ⅰ））;
            } 其他 {
                second.add（set.get（ⅰ））;
            }
        }
        如果（first.size（）＆其中; set.size（）＆安培;＆安培; second.size（）＆其中; set.size（））{
            如果（output.contains（第一+！+二）及和放大器;！output.contains（第二++先））{
                output.add（第一++二）;
            }
        }
        first.clear（）;
        second.clear（）;
    }
    返回输出;
}
 

输出：

  [1] [1，4，3]
[3] [1，4,1]
[3,1] [1，4]
[4] [1，3,1]
[4,1] [1,3]
[4，3] [1,1]
[4，3，1] [1]
 

这是沿着你要找的线路？如果没有，让我知道，我会做出调整或添加评论是必要的。

I am working with a linked list that I created which contains a set of numbers as data. I need to find a way to test every possible two-set partition of this list for something, and to do that, I need to break the list into every possible two-set combination. Order is not important and there will be duplicates.

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}

A list of 4 numbers is not difficult, but things become more complicated as the list grows larger, and I am having trouble seeing a pattern. Can anyone help me find an algorithm for this?

Edit:

Sorry, I didn't see the question. This is what I have tried so far. My loop structure is wrong. When I figure out what I am doing after trying on a regular array, I will extend the algorithm to fit my linked list.

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] + " ");
            }



        }
    }

}

解决方案

Code:

public static void main(String[] args) {
    for(String element : findSplits(list)) {
        System.out.println(element);
    }        
}

static ArrayList<String> findSplits(ArrayList<Integer> set) {
    ArrayList<String> output = new ArrayList();
    ArrayList<Integer> first = new ArrayList(), second = new ArrayList();
    String bitString;
    int bits = (int) Math.pow(2, set.size());
    while (bits-- > 0) {
        bitString = String.format("%" + set.size() + "s", Integer.toBinaryString(bits)).replace(' ', '0');
        for (int i = 0; i < set.size(); i++) {
            if (bitString.substring(i, i+1).equals("0")) {
                first.add(set.get(i));
            } else {
                second.add(set.get(i));
            }
        }
        if (first.size() < set.size() && second.size() < set.size()) {
            if (!output.contains(first + " " + second) && !output.contains(second + " " + first)) {
                output.add(first + " " + second);
            }
        }
        first.clear();
        second.clear();
    }
    return output;
}

Output:

[1] [1, 4, 3]
[3] [1, 4, 1]
[3, 1] [1, 4]
[4] [1, 3, 1]
[4, 1] [1, 3]
[4, 3] [1, 1]
[4, 3, 1] [1]

Is this along the lines of what you were looking for? If not, let me know and I will make adjustments or add comments as necessary.

这篇关于算法找到一个列表的所有可能分割的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！