2007-08-15

实践递归

关键字: 递归

描述：1,2,3......n 从n中取出r个数。
例如：n=5，r=3
1-2-3，1-2-4，1-2-5，1-3-4，1-3-5，1-4-5
2-3-4，2-3-5，2-4-5
3-4-5

下面是我的解决方法，还有其他的方法么？

java 代码
  1. import java.util.ArrayList;   
  2. import java.util.Collections;   
  3. import java.util.HashSet;   
  4. import java.util.Iterator;   
  5. import java.util.List;   
  6. import java.util.Set;   
  7. import java.util.Stack;   
  8.   
  9. public class Combination {   
  10.     private List result;   
  11.     private int r = 4;   
  12.     private int n = 7;   
  13.   
  14.     public Combination() {   
  15.         result = new ArrayList();   
  16.         Stack permutation = new Stack();   
  17.         for (int i = 1; i < r + 1; i++) {   
  18.             permutation.push(i);   
  19.         }   
  20.         result.add(permutation);   
  21.     }   
  22.   
  23.     public static void main(String[] args) {   
  24.         Combination com = new Combination();   
  25.         com.compose(com.result.size());   
  26.         com.removeExisted();   
  27.         com.sortList();   
  28.         com.print();   
  29.     }   
  30.   
  31.     private void sortList() {   
  32.         List sorted = new ArrayList();   
  33.         for (Iterator iter = result.iterator(); iter.hasNext();) {   
  34.             Stack element = (Stack) iter.next();   
  35.             StringBuffer sb = new StringBuffer();   
  36.             for (Iterator iterator = element.iterator(); iterator.hasNext();) {   
  37.                 int i = (Integer) iterator.next();   
  38.                 sb.append(i + "-");   
  39.             }   
  40.             sb.deleteCharAt(sb.length()-1);   
  41.             sorted.add(sb.toString());   
  42.         }   
  43.         Collections.sort(sorted);   
  44.         result=sorted;   
  45.     }   
  46.   
  47.     private void removeExisted() {   
  48.         Set set = new HashSet();   
  49.         for (Iterator iter = result.iterator(); iter.hasNext();) {   
  50.             set.add(iter.next());   
  51.         }   
  52.         result.clear();   
  53.         result.addAll(set);   
  54.     }   
  55.   
  56.     private void print() {   
  57.         System.out.println("result:");   
  58.         for (Iterator iter = result.iterator(); iter.hasNext();) {   
  59.             String element = (String) iter.next();   
  60.             System.out.println(element);   
  61.         }   
  62.     }   
  63.   
  64.     private void compose(int size) {   
  65.         for (int i = 0; i < size; i++) {   
  66.             Stack element = (Stack) result.get(i);   
  67.             int max = (Integer) element.peek();   
  68.             if (max == n) {   
  69.                 return;   
  70.             } else {   
  71.                 Stack copyedS = copyStack(element);   
  72.                 ++max;   
  73.                 createNewComS(copyedS, max);   
  74.             }   
  75.         }   
  76.         compose(result.size());   
  77.     }   
  78.   
  79.     private void createNewComS(Stack original, int max) {   
  80.         for (int i = 0; i < r; i++) {   
  81.             Stack copyedS = copyStack(original);   
  82.             copyedS.remove(i);   
  83.             copyedS.push(max);   
  84.             result.add(copyedS);   
  85.         }   
  86.     }   
  87.   
  88.     private Stack copyStack(Stack element) {   
  89.         Stack copyed = new Stack();   
  90.         for (int i = 0; i < element.size(); i++) {   
  91.             int num = (Integer) element.get(i);   
  92.             copyed.push(num);   
  93.         }   
  94.         return copyed;   
  95.     }   
  96. }   
评论
bill.end
搜索本博客
博客分类
最近加入圈子
存档
最新评论
  • Ext Grid
    本地两个都可以用的
    -- by zhangtianqi
  • Ext Grid
    这个是跨域执行的，服务器和执行文件不再一起放着的，所以用ScriptTagPro ...
    -- by zhangtianqi
  • Ext Grid
    感谢楼主..这虽然是个小问题. 但是困扰了几天.. (感激中....)
    -- by yangfengjob