求一个集合S中m个元素的所有排列以及一个数组A的全排列—递归实现版完整代码

佚名 6年前 (2019-05-13) 随笔 1867人围观抢沙发百度已收录

　　说明，本文全文代码均用dart语言实现。

　　求一个集合S中m个元素的所有排列情况，并打印，非常适合用递归的思路实现。本文给出了两种实现方法，一种是给定的填充排列数组长度是固定的，一种是可变长度的。两种方法主要思路是一样的，只是实现细节上略有差异。具体代码如下：

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

 1 void permute<E>(Set<E> s, int m) {  2   if (m < 0 || m > s.length) throw StateError('m is not in [0, ${s.length}]');  3 
 4   _fill(<E>[], s, m);  5   print('-------------------');  6   _fillFixed(List<E>(m), s, 0, m);  7 }  8 
 9 10 
11 void _fill<E>(List<E> pm, Set<E> s, int m) { 12   if (pm.length < m) { 13     for (var e in s) { 14  pm.add(e); 15  _fill(pm, _rest(s, e), m); 16  } 17   } else { 18  print(pm); 19  } 20   if (pm.isNotEmpty) pm.removeLast(); 21 } 22 
23 void _fillFixed<E>(List<E> pm, Set<E> s, int i, int m) { 24   if (i < m) { 25     for (var e in s) { 26       pm[i] = e; 27       _fillFixed(pm, _rest(s, e), i + 1, m); 28  } 29   } else { 30  print(pm); 31  } 32 } 33 
34 Set _rest<E>(Set<E> s, E e) { 35   var t = s.toSet(); 36  t.remove(e); 37   return t; 38 }

　　如果求一个集合的全排列，如果是集合的话，其实在上面的函数permute，将m的值设为集合s的长度即可：

1 void permuteAll2<E>(Set<E> s) => permute(s, s.length);

　　如果求一个数组的全排列情况（假设数组中元素不重合），可以不像集合那样，还需要额外申请空间，直接利用数组本身即可完成：

 1 void permuteAll(List a, int k) {  2   if (k < a.length - 1) {  3     for (int i = k; i < a.length; i++) {  4       if (i != k) _swap(a, k, i);  5       permuteAll(a, k + 1);  6       if (i != k) _swap(a, k, i);  7  }  8   } else {  9  print(a); 10  } 11 } 12 
13 void _swap(List a, int i, int j) { 14   var t = a[i]; 15   a[i] = a[j]; 16   a[j] = t; 17 }

　　具体思路，比较简单，直接查看代码即可，或者参照网上的讲解，这里不再赘述了。有兴趣的也可以直接debug，可以看每一步的操作。

　　最后，验证代码如下：

1 void main() { 2   var s = {1, 2, 3}; 3   permute(s, 3); 4   print('---------------------\n'); 5   permuteAll(s.toList(), 0); 6   print('---------------------\n'); 7  permuteAll2(s); 8 }