算法 集合的所有子集 全排列

Question

{1,2,3} 的所有排列组合方式
{{1},{2},{3}}

{{1},{2,3}}

{{1,2},{3}}

{{1,3},{2}}

{{123}}
请大家给个想法 或者 算法实现

Answer 1

public List<List<List<Integer>>> allSubsetPermutation(int[] nums){
    if(nums == null || nums.length == 0)
        return null;
    Queue<List<List<Integer>>> q = new LinkedList<>();
    q.add(new LinkedList<>());

    for(int n: nums){
        int size = q.size();
        while(size-- > 0){
            List<List<Integer>> list = q.poll();
            for(int i = 0; i < list.size(); i++){
                List<List<Integer>> l = deepClone(list);
                l.get(i).add(n);
                q.offer(l);
            }
            list.add(new LinkedList<>(Arrays.asList(n)));
            q.offer(list);
        }
    }
    return new LinkedList<>(q);
}

private List<List<Integer>> deepClone(List<List<Integer>> list){
    List<List<Integer>> l = new LinkedList<>();
    for(List<Integer> li: list)
        l.add(new LinkedList<>(li));
    return l;
}

@Test
public void test(){
    List<List<List<Integer>>> l = null;
    l = allSubsetPermutation(new int[]{1});
    l = allSubsetPermutation(new int[]{1, 2});
    l = allSubsetPermutation(new int[]{1, 2, 3});
    l = allSubsetPermutation(new int[]{1, 2, 3, 4});
    return;
}

Answer 2

这个我想到高中的排列组合，用的是隔板法(不太记得是不是叫这个)。
比如，隔板是说在1|2|3|4 数字中间放的分隔板。
分成一个集合，不用隔板
分成两个集合，放一个隔板，共C(n-1,1),比如{1|234} {12|34} {123|4}
分成k个集合，放k-1个隔板，共C(n-1,k-1)种。

然后想如何实现隔板，给隔板编号1 , 2 , ... , n-1
于是每次放k个隔板意味着从n-1个数中取出k个数字，就是组合数，可以用回溯遍历出来

seq[] 放k的数字
seq[]=-1表示这个位置没有数字
DFS(index){
    if(index==k) {print(); return;}
    for(int i=1;i<=n-1;++i){
        if (seq[index]==-1 ){
            seq[index]=i; // 
            DFS(index+1)
            seq[index]=-1
        } 
    }
}
print(){
    int index=0;
    for(int i=1;i<=n;++i){
        printf(i);
        if(i==seq[index]){index++; print( | )}
    }
}
DFS(1)

讲的好，如果不存储全部的子集的话，每次维护/保存当前i的子集的序列，每次加一个i+1时，只需要输出i，和将i加到当前序列里面就可以了。

DFS(int num){
    print( {num} );
    for(int i=0;i<seq.size();++i){
        seq[i].add( num ); // 把num加入当前队列
        print( { );        // 便于显示观看
        for(intj=0;j<seq[i].size();++j)
            prinf( seq[i][j] );
        prinf( } );        // 便于显示观看
    }
    DFS(num+1);
}

如果不存储全部的子集的话,只需要复制seq，再添加num到其中一个seq中去即可，再加一个{num}。

咦？其实这个也可以直接一个循环，不用DFS还要浪费栈，因为num是从1到n没有变化的呀！

for (int num=1; num<=n; ++num)
{
    print( {num} );
    for(int i=0;i<seq.size();++i){
        seq[i].add( num ); // 把num加入当前队列
        print( { );        // 便于显示观看
        for(intj=0;j<seq[i].size();++j)
            prinf( seq[i][j] );
        prinf( } );        // 便于显示观看
    }
}

Answer 3

public class Solution {

public List<List<Integer>> permute(int[] num) {
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    permute(result, num, 0);
    return result;
}

private void permute(List<List<Integer>> result, int[] array, int start) {
    if (start >= array.length) {
        List<Integer> current = new ArrayList<Integer>();
        for (int a : array) {
            current.add(a);
        }
        result.add(current);
    } else {
        for (int i=start; i<array.length; i++) {
            swap(array, start, i);
            permute(result, array, start+1);
            swap(array, start, i);
        }
    }
}

private void swap(int[] array, int i, int j) {
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

}

Answer 4

递归大法好：

def sub_sets(a):
    """
    find out all sub sets of specified collection.
    :param: a  - a set of elements
    :return: - a list of sub-sets. Each sub-set is a list of sets.
    """
    if len(a) == 0:
        return [] # empty set has no sub-sets
    elif len(a) == 1:
        return [[a]]
    else:
        x = a.pop()
        rest_sub_sets = sub_sets(a)

        # add single subset {x}
        all_sub_sets = [copy_list_add(m, {x}) for m in rest_sub_sets ]

        # add single element x to all subsets
        for ss in rest_sub_sets:
            for i in range(0, len(ss)):
                ss_copy = ss[:]
                ss_copy[i] = ss_copy[i].copy()
                ss_copy[i].add(x)
                all_sub_sets.append(ss_copy)

        return all_sub_sets

def copy_list_add(a, x):
    a_copy = a[:]
    a_copy.append(x)
    return a_copy

附测试代码：

def sub_sets_to_str(a):
    lines = []
    for l in a:
        parts = []
        for s in l:
            parts.append('{%s}' % ','.join(sorted(map(str, list(s)))))

        lines.append('[%s]' % ', '.join(sorted(parts)))

    return "\n".join(sorted(lines))

class SubSetTestCase(unittest.TestCase):
    def testEmpty(self):
        self.assertSubSetsEqual([], sub_sets(set()))

    def testOne(self):
        self.assertSubSetsEqual([[{1}]], sub_sets({1}))

    def testTwo(self):
        self.assertSubSetsEqual([
            [{1}, {2}],
            [{1,2}]
        ], sub_sets({1,2}))

    def testThree(self):
        result = [
            [{1}, {2}, {3}],
            [{1}, {2,3}],
            [{1,2}, {3}],
            [{1,3}, {2}],
            [{1,2,3}]
        ]
        self.assertSubSetsEqual(result, sub_sets({1,2,3}))

    def testFour(self):
        result = [
            [{1,2,3,4}],
            [{1}, {2,3,4}],
            [{1,2}, {3,4}],
            [{1,2,3}, {4}],
            [{1,3}, {2,4}],
            [{1,4}, {2,3}],
            [{1}, {2}, {3,4}],
            [{1,2}, {3}, {4}],
            [{1,3}, {2}, {4}],
            [{1,4}, {2}, {3}],
            [{1}, {2,3}, {4}],
            [{1}, {2}, {3}, {4}],
        ]
        self.assertSubSetsEqual(result, sub_sets({1,2,3,4}))

    def assertSubSetsEqual(self, a, b):
        a_str = sub_sets_to_str(a)
        b_str = sub_sets_to_str(a)
        if 1 or a_str != b_str:
            print
            print ' --- a --- '
            print a_str
            print ' --- b --- '
            print b_str
        return unittest.TestCase.assertEqual(self, a_str, b_str)


if __name__ == '__main__':
    unittest.main()

测试结果：

 --- a --- 

 --- b --- 

.
 --- a --- 
[{1,2,3,4}]
[{1,2,3}, {4}]
[{1,2}, {3,4}]
[{1,2}, {3}, {4}]
[{1,3}, {2,4}]
[{1,3}, {2}, {4}]
[{1,4}, {2,3}]
[{1,4}, {2}, {3}]
[{1}, {2,3,4}]
[{1}, {2,3}, {4}]
[{1}, {2}, {3,4}]
[{1}, {2}, {3}, {4}]
 --- b --- 
[{1,2,3,4}]
[{1,2,3}, {4}]
[{1,2}, {3,4}]
[{1,2}, {3}, {4}]
[{1,3}, {2,4}]
[{1,3}, {2}, {4}]
[{1,4}, {2,3}]
[{1,4}, {2}, {3}]
[{1}, {2,3,4}]
[{1}, {2,3}, {4}]
[{1}, {2}, {3,4}]
[{1}, {2}, {3}, {4}]
.
 --- a --- 
[{1}]
 --- b --- 
[{1}]
.
 --- a --- 
[{1,2,3}]
[{1,2}, {3}]
[{1,3}, {2}]
[{1}, {2,3}]
[{1}, {2}, {3}]
 --- b --- 
[{1,2,3}]
[{1,2}, {3}]
[{1,3}, {2}]
[{1}, {2,3}]
[{1}, {2}, {3}]
.
 --- a --- 
[{1,2}]
[{1}, {2}]
 --- b --- 
[{1,2}]
[{1}, {2}]
.
----------------------------------------------------------------------
Ran 5 tests in 0.006s

OK

Answer 5

1、深度优先搜索实现
2、状态压缩用位表示集合

int set = (1<<n)-1;// 1111111....
for (int sub = set; sub; sub = set & (sub-1)) {
    //....
}

可以实现对一个集合的所有子集的枚举

Answer 6

用位向量啊
若对应位置1，则表示后面插一个板

def work(n):
    for vector in xrange(1<<(n-1)):
        result = []
        for i in xrange(n):
            result.append(str(i+1))
            if (1 << i) & vector:
              result.append('|')
        print ' '.join(result)

work(3)

output:

1 2 3
1 | 2 3
1 2 | 3
1 | 2 | 3

Answer 7

递归实现就可以了