回溯法/解空间树 排列树
-
初始时选择第0索引结点 选择第i个元素之后形成的父节点,父节点的孩子结点,通过父结点的第i和第j元素交换,轮流把第j个元素放到第i位,形成子结点
package xcrj.kchalgorithm.backtracking; import java.util.Arrays; /** * 排列树 * 达到要求的排列,所有元素都在;把那个元素放到第1位,把那个元素放到第2位,依次类推 * <p> * 选择第i个元素之后形成的父节点,父节点的孩子结点,通过父结点的第i和第j元素交换,轮流把第j个元素放到第i位,形成子结点 */ public class PermutationTree { /** * @param xs * @param i * @param len */ public static void permutationTree(int[] xs, int i, int len) { // 到达叶子结点输出 if (i == len) { System.out.println(Arrays.toString(xs)); } // 到达非叶子结点,生成i结点的所有孩子结点j else { // !选择第i个元素之后形成的父节点,父节点的孩子结点,通过父结点的第i和第j元素交换,轮流把第j个元素放到第i位,形成子结点 for (int j = i; j < len; j++) { // 交换,通过父结点的第i和第j元素交换,轮流把第j个元素放到第i位,形成子结点 int temp = xs[j]; xs[j] = xs[i]; xs[i] = temp; // 深度优先遍历操作孩子结点 permutationTree(xs, i + 1, len); // 交换回来 int temp2 = xs[j]; xs[j] = xs[i]; xs[i] = temp2; } } } public static void main(String[] args) { int[] xs = { 1, 2, 3}; permutationTree(xs, 0, xs.length); } }
时间复杂度
O ( n ! ) O(n!) O(n!) 第0层 第1层:第1位有n种选择 第2层:第2位有n-1种选择(第1位的数字已经确定) 第3层:第3位有n-2种选择 … 第n层:第n位有1种选择
要得到1个完整的排列,从根到叶子一步步完成,所以时间复杂度是 O ( n ! ) O(n!) O(n!)