java - java中所有可能的子集以不同的顺序

Question

我有一个集合 =(1, 2, 3)，我需要获取具有不同序列（具有重复元素）的集合的所有可能子集。输出外观：

1
2
3
1,2
1,3
2,1
2,3
3,1
3,2
1,2,3
1,3,2
2,1,3
2,3,1
3,1,2
3,2,1

请问有人可以帮我吗？谢谢

Answer 1

如果您想要subsets，那么 Google Guava 为您提供了一种方法：

http://docs.guava-libraries.googlecode.com/git/javadoc/com/google/common/collect/Sets.html#powerSet(java.util.Set)

但是在您的示例中，您有一些重复的集合（请记住，集合是无序的）。因此，您可能还希望获得每个子集的所有可能排列：

http://docs.guava-libraries.googlecode.com/git/javadoc/com/google/common/collect/Collections2.html#permutations(java.util.Collection)

Answer 2

该问题可以通过使用按位运算找到所有组合来解决。

这个想法是：生成给定数组（集合）的所有子集，这个集合称为幂集。对于每个子集（组合），也找到它的排列。

请参阅以下教程，了解如何使用位运算找到所有组合。http://www.codechef.com/wiki/tutorial-bitwise-operations

    void PERMUTE()
    {
        /*PERMUTATION FUNCTION THAT PERMUTES THE SUBSET ARRAY*/
    }
    public static void main(String[] args) 
    {
        // TODO code application logic here
        int Set[]={1,2,3};
        int n=Set.length;

       for (int i = 0; i <= (1 << n); ++i)
       {

           System.out.print("[");
           int subsetSz=0;
           int A[]=new int[100];
            for (int j = 0; j < n; ++j)
            {
                if ((i & 1 << j)!=0)
                {
                    System.out.print(Set[j]+",");
                    A[subsetSz++]=Set[j];

                }
            }
            System.out.println("]");
            /*Permute the subset*/
            if(subsetSz>1)
            {
                PERMUTE(A);
            }
        }
    }