一个软件公司的面试题

把一个数组里的数组合全部列出了  比如1 2 列出来为 1, 2 ,12,21, 
尽量简洁.

解决方案 »

  1.   

    在不考虑效率，重复的前提下  public static void main(String[] args) throws Exception {
        String[] array = new String[] {
            "1", "2", "3", "4"
        };
        listAll(Arrays.asList(array), "");
      }  public static void listAll(List candidate, String prefix) {
        if (candidate == null || candidate.isEmpty()) {
          System.out.println(prefix);
        }
        
        for (int i = 0; i < candidate.size(); i++) {
          List temp = new LinkedList(candidate);
          listAll(temp, prefix + temp.remove(i));
        }
      }=====输出=====
    1234
    1243
    1324
    1342
    1423
    1432
    2134
    2143
    2314
    2341
    2413
    2431
    3124
    3142
    3214
    3241
    3412
    3421
    4123
    4132
    4213
    4231
    4312
    4321
      

  2.   

    如果个数不固定，比如lz 1,2 ==> 1,2,12,21  public static void main(String[] args) throws Exception {
        String[] array = new String[] {
            "1", "2", "3", "4"
        };
        listAll(Arrays.asList(array), "");
      }  public static void listAll(List candidate, String prefix) {
    //    if (candidate.isEmpty()) {
          System.out.println(prefix);
    //    }
        
        for (int i = 0; i < candidate.size(); i++) {
          List temp = new LinkedList(candidate);
          listAll(temp, prefix + temp.remove(i));
        }
      }=====输出=====
    1
    12
    123
    1234
    124
    1243
    13
    132
    1324
    134
    1342
    14
    142
    1423
    143
    1432
    2
    21
    213
    2134
    214
    2143
    23
    231
    2314
    234
    2341
    24
    241
    2413
    243
    2431
    3
    31
    312
    3124
    314
    3142
    32
    321
    3214
    324
    3241
    34
    341
    3412
    342
    3421
    4
    41
    412
    4123
    413
    4132
    42
    421
    4213
    423
    4231
    43
    431
    4312
    432
    4321
      

  3.   

    回复人：88324877(看懂请给分，你好我也好。) ( ) 信誉：100 2006-12-29 23:29:04 得分:0
    ?
    这里是考数据结构里图的知识吧。====================
    我认为是树上面用List纯属偷懒，int[]什么也可以，循环的时候，假如当前取出的内容(list.remove(i)，相当于get(i)然后remove)，在prefix里面，则continue.
      

  4.   

    先判断数组的元素是否有重复(即相等)?
    有重复->递归+组合
    无重复->递归+排列暂时先讨论无重复的情况,数组的元素看作是一个集合,假设为n个,则
    1):  取一个元素的情况,有n种可能性;
    2):  取两个元素的情况,则有n*(n-1)/2种可能性,而取得的两个数又可以进行全排列,所以共有2!*n*(n-1)/2=n*(n-1)种可能性;
    ......
    n-1):  取n-1个元素的情况,有n种可能性,而取得的n-1个数又可以进行全排列,所以共有n*(n-1)!=n!;
    n):  取n个元素的情况,有1种,一个全排列,共有n!种;所有的可能性为从第1)步到第n)步的可能性之和。编程用递归也不容易，数组元素如果有重复，那就要用到《组合数学》中的定理了。限于时间，不再赘述。
      

  5.   

    这个考代码的话还是蛮简单的，shine333(enihs) 的回答我觉得挺详细的了，
    考思想，那就不知道所以然了，进来学习学习
      

  6.   

    shine333(enihs) 你的程序有我怎么一运行,就报错呀,
      

  7.   

    我编译了下也报错,刚开始学java,想看看你们的代码
    listAll.java:1: 'class' or 'interface' expected
     public static void main(String[] args) throws Exception
                   ^
    1 error
      

  8.   

    排列Pn(m)首先去掉相同的数,然后根据排列的公式算出所有的排列，去掉位数2位以上的数的各个位上的数字都在1位数的数字集合里都出现过，
    最后就是剩下的数组为A,元素个数为N,最后在根据排列公式算出所有的可能！
    Pn(1)=n!/(n-1)!
    Pn(2)=n!/(n-2)!
    Pn(3)=n!/(n-3)!
    ...
    Pn(n)=n!/(n-n)! (n是数组中有多少个不同的数）
      

  9.   

    回复人：cooljelly() ( ) 信誉：100 2006-12-30 12:26:56 得分:0
    ? 我编译了下也报错,刚开始学java,想看看你们的代码
    listAll.java:1: 'class' or 'interface' expected
    public static void main(String[] args) throws Exception
    ^
    1 error外面写个class
    public class Test {
      pubilc static void main .......
    }
      

  10.   

    排列Pn(m)首先去掉相同的数, ......=================================大家根本不需要考虑重复不重复这件事情，取的时候，就只有位置信息，而不管他们的数值是多少。最后出来的结果，必然是
    1
    12
    123
    1234
    124
    1243
    13
    ......
    只不过这里1，2的含义不是数值，而是位置信息
      

  11.   

    shine333  谢谢你呀,能不能加你的QQ呀?