请问这个组合算法如何实现?

Question

刚看到的一道面试题目,感觉不难,但写代码的时候却没写出来(真是菜啊)...

有一个5位数,每位上的可能性分别是:
1,2,3
2,3,4
3
9,8
3
请问有多少种5位数的可能性?并枚举出所有可能性.请用程序实现,语言不限

Answer 1

三重循环，共有3x3x2种可能性

 @Test
    public void test() {
        int[] a = new int[]{1, 2, 3};
        int[] b = new int[]{2, 3, 4};
        int[] c = new int[]{9, 8};
        String result = "";
        String tmp1 = "";
        String tmp2 = "";
        for (int i : a) {
            result += i;
            for (int j : b) {
                tmp2 = result;
                result = result + j + 3;
                for (int k : c) {
                    tmp1 = result;
                    result = result + k + 3;
                    System.out.println(result);
                    result = tmp1;
                }
                result = tmp2;
            }
            result = "";
        }
    }

更新

这是一个在更多情境下都普适的问题，已经将此问题总结成博客，地址为

http://yanwushu.sinaapp.com/cartesian_product/

此问题抽象出来应该是：求多个集合的笛卡尔积（笛卡尔积应该是针对两个集合的概念，因为这里不知道如何表达，所以说多个集合的笛卡尔积，其实这是不准确的），下面的思路是，先用两重循环实现求两个集合的笛卡尔积，然后根据此，实现多个集合的笛卡尔积。

    @Test
    public void test() {
        String[] a1 = new String[]{"1", "2", "3"};
        String[] a2 = new String[]{"3"};
        String[] a3 = new String[]{"2", "3", "4"};
        String[] a4 = new String[]{"3"};
        String[] a5 = new String[]{"9", "8"};
        List<String[]> list = new ArrayList<String[]>();
        list.add(a1);
        list.add(a2);
        list.add(a3);
        list.add(a4);
        list.add(a5);
        String[] result = getNDis(list);
        for (String item : result)
            System.out.println(item);
    }

    //N个集合的笛卡尔积
    public String[] getNDis(List<String[]> a) {
        String[] result = a.get(0);
        for (int i = 1; i < a.size(); i++)
            result = getDis(result, a.get(i));
        return result;
    }

    //两个集合的笛卡尔积
    public String[] getDis(String[] a, String[] b) {
        String[] result = new String[a.length * b.length];
        int k = 0;
        for (String i : a)
            for (String j : b) {
                result[k] = i + j;
                k++;
            }
        return result;
    }