{1,2,3} 的所有排列组合方式
{{1},{2},{3}}
{{1},{2,3}}
{{1,2},{3}}
{{1,3},{2}}
{{123}}
请大家给个想法 或者 算法实现
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;
}
递归大法好：
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
OKpublic 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;
}}
用位向量啊
若对应位置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 | 31、深度优先搜索实现
2、状态压缩用位表示集合
int set = (1<<n)-1;// 1111111....
for (int sub = set; sub; sub = set & (sub-1)) {
//....
}可以实现对一个集合的所有子集的枚举
递归实现就可以了
这个我想到高中的排列组合，用的是隔板法(不太记得是不是叫这个)。
比如，隔板是说在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( } ); // 便于显示观看
}
}