5

您好，我希望这段代码是非递归的，我该怎么做？

public class test {

    public static void main(String[] args) {
        int[] array = new int[]{0, 1, 2,3};
        int size = 2;
        int[] tmp = new int[size];
        //Arrays.fill(tmp, -1);
        generateCombinations(array, 0, 0, tmp);
    }

    private static void generateCombinations(int[] array, int start, int depth, int[] tmp) {

        if (depth == tmp.length) {
            for (int j = 0; j < depth; j++) {
                System.out.print(array[tmp[j]]);

            } System.out.println();
            return;
        }
        for (int i = start; i < array.length; i++) {
            tmp[depth] = i;
            generateCombinations(array, i + 1, depth + 1, tmp);
        }

    }
}

它从特定数字生成所有组合。

4

2 回答 2

0

每个递归都可以重写为迭代，反之亦然。你只需要遵循一个通用的算法：

  1. 确定递归的基本情况。达到基本情况时，会导致递归结束。每个递归都必须有一个定义的基本情况。此外，每个递归调用都必须朝着基本情况前进（否则递归调用将无限执行）。在我们的示例中，基本情况是 n == 0。
  2. 实现一个循环，直到达到基本情况。
  3. 在基本情况下取得进展。将新参数发送到循环顶部而不是递归方法。

这背后是保持不变条件的概念。

于 2013-12-05T07:29:54.483 回答
0

尝试这个：

public class Test {
    private final int[] array;
    private final int[] tmp;

    private Test(int[] array, int size) {
        tmp = new int[size];
        this.array = array;
    }

    public static void main(String[] args) {
        Test t = new Test(new int[] {0, 1, 2, 3}, 2);
        t.generateCombinations();
    }

    /**
     * Print the selection.
     */
    private void print() {
        for (int i : tmp) {
            System.out.print(array[i]);
        }
        System.out.println();
    }

    /**
     * Set values in tmp for indices startIndex, ..., (tmp.length-1)
     * to startValue, ..., (startValue-startIndex + tmp.length-1)
     * @param startIndex
     * @param startValue 
     */
    private void initMin(int startIndex, int startValue) {
        final int offset = startValue - startIndex;
        for (int i = startIndex; i < tmp.length; i++) {
            tmp[i] = i+offset;
        }
    }

    private void generateCombinations() {
        if (tmp.length == 0) return;
        initMin(0, 0);
        print();

        final int maxIndex = tmp.length-1;
        int index = maxIndex;
        final int z = array.length-tmp.length;

        while (index >= 0) {
            if (tmp[index] == index+z) {
                index--;
            } else {
                if (tmp[index]== index+z-1) {
                    // only value at index changes
                    tmp[index]++;
                    index--;
                } else {
                    initMin(index, tmp[index]+1);
                    index = maxIndex;
                }

                print();
            }
        }
    }
}

该算法基于以下观察： tmp[i]必须最多(i+array.length-tmp.length)

该算法总是在最后一个位置添加 1，这仍然是可能的，并将以下位置的值设置为最小的可能值。

于 2013-12-05T05:34:25.333 回答