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

Question

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

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



        }
    }

}

Answer 1

因此，除了互补子集之外，您正在寻找给定集合的所有(适当的)子集。如果您的列表有 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
       }
    }
}