algorithm - 从给定长度的数组中排列整数

Question

我面试了一个问题，之后我测试了我的代码，发现它是错误的。 不擅长递归。但我无法弄清楚问题所在。

题目是:给定一个范围为0~9的数组，以及一个长度，比如3；产生 给定数组中给定长度的所有整数排列。 因此，例如: 排列应为:012、013、014、...、345、346... 下面是我的java代码，问题出在哪里？ (我认为是索引或偏移量部分) 而且，如果有更好的解决方案!

public void NumPermutation(int[] list, int offset, int[] temp, int index){
    if(index == 4){
       printarray(temp);
    }

    for(int count = offset; count < list.length; count++){
        temp[index++] = list[count];
        int te = list[offset];
        list[offset] = list[count];
        list[count] = te;
        NumPermutation(list, offset, temp, index);
        index -= 1;
    }
}

public void test(int len){
    int[] list = {0,1,2,3,4,5,6,7,8,9};
    int[] temp = new int[4];
    int index = 0, offset = 0;
    NumPermutation(list, offset, temp,index);
}

问题是，偏移量可能每次都增加并且 它甚至无法到达最后的数字。

Answer 1

你需要:

• 将 offset+1 传递给递归调用。

• 在 if 语句中返回。

• 在递归调用后反转交换。

• 将 4 替换为 temp.length 以获得更通用的解决方案。

• 也最好将index++, index, index -= 1替换为index, index + 1 什么都没有。

这会导致此代码:(将 printarray 替换为标准打印方法，假设这是 Java)

public static void NumPermutation(int[] list, int offset, int[] temp, int index){
    if(index == temp.length) {
       System.out.println(Arrays.toString(temp));
       return;
    }

    for(int count = offset; count < list.length; count++){
        temp[index] = list[count];

        // swap
        int te = list[offset];
        list[offset] = list[count];
        list[count] = te;

        NumPermutation(list, offset + 1, temp, index + 1);

        // reverse swap
        te = list[offset];
        list[offset] = list[count];
        list[count] = te;
    }
}

Live demo .