JAVA用递归实现全排列算法的示例代码

发布时间：2024/03/08

全排列算法是一个经典的、递归思想的算法，它将一组数据按照一定顺序排列，使得每个数据都和其他数据组成一组不同的排列。在JAVA中，我们可以利用递归的思想来实现全排列算法。以下是针对该问题的完整攻略：

1. 全排列算法的基本原理：

全排列算法的基本原理是：对于一个长度为n的序列，全排列可分解为两部分：固定第一个元素，对剩余的n-1个元素进行全排列；再将每一个排列中的第一个元素和其他元素交换位置得到的子排列进行递归全排列。

2. JAVA实现全排列算法的代码：

public class FullPermutation {
  public static void main(String[] args) {
      String[] arr = {"a", "b", "c"};
      permutation(arr, 0, arr.length - 1);
  }

  // 递归实现数组全排列
  public static void permutation(String[] arr, int start, int end) {
      if (start == end) {
          // 输出一组排列
          for (String str : arr) {
              System.out.print(str + " ");
          }
          System.out.println();
      } else {
          for (int i = start; i <= end; i++) {
              // 将当前位置和其他位置交换
              swap(arr, i, start);
              permutation(arr, start + 1, end);
              // 还原当前位置
              swap(arr, i, start);
          }
      }
  }

  // 交换数组中两个位置的元素
  public static void swap(String[] arr, int i, int j) {
      String temp = arr[i];
      arr[i] = arr[j];
      arr[j] = temp;
  }
}

在代码中，我们通过递归地调用permutation方法，实现了全排列算法。该方法的整个递归过程，包括两个步骤：对于剩余的元素进行全排列和将每一个排列中第一个元素和其他元素交换位置得到的子排列进行递归全排列。具体来说，当start等于end时，说明已经对所有元素进行了一次全排列，此时输出一组排列；否则，对剩余未排列的元素进行全排列时，每次都将当前元素和其他元素交换位置，并进行递归操作，最后还需要还原当前元素的位置。

3. 示例说明：

示例1：

现有一个序列{"a", "b", "c", "d"}，请使用JAVA递归实现它的全排列。

该问题的具体步骤如下：

以a为首元素，对{"b", "c", "d"}进行全排列，得到一个子问题；
以b为首元素，对{"a", "c", "d"}进行全排列，得到一个子问题；
以c为首元素，对{"a", "b", "d"}进行全排列，得到一个子问题；
以d为首元素，对{"a", "b", "c"}进行全排列，得到一个子问题；
将每个子问题中的结果进行汇总，得到所有排列。

使用JAVA递归实现该问题的代码如下：

public class FullPermutation {
  public static void main(String[] args) {
      String[] arr = {"a", "b", "c", "d"};
      permutation(arr, 0, arr.length - 1);
  }

  // 递归实现数组全排列
  public static void permutation(String[] arr, int start, int end) {
      if (start == end) {
          // 输出一组排列
          for (String str : arr) {
              System.out.print(str + " ");
          }
          System.out.println();
      } else {
          for (int i = start; i <= end; i++) {
              // 将当前位置和其他位置交换
              swap(arr, i, start);
              permutation(arr, start + 1, end);
              // 还原当前位置
              swap(arr, i, start);
          }
      }
  }

  // 交换数组中两个位置的元素
  public static void swap(String[] arr, int i, int j) {
      String temp = arr[i];
      arr[i] = arr[j];
      arr[j] = temp;
  }
}

示例2：

现有一个长度为5的序列{1, 2, 3, 4, 5}，请使用JAVA递归实现它的全排列。

该问题的具体步骤如下：

以1为首元素，对{2, 3, 4, 5}进行全排列，得到一个子问题；
以2为首元素，对{1, 3, 4, 5}进行全排列，得到一个子问题；
以3为首元素，对{1, 2, 4, 5}进行全排列，得到一个子问题；
以4为首元素，对{1, 2, 3, 5}进行全排列，得到一个子问题；
以5为首元素，对{1, 2, 3, 4}进行全排列，得到一个子问题；
将每个子问题中的结果进行汇总，得到所有排列。

使用JAVA递归实现该问题的代码如下：

public class FullPermutation {
  public static void main(String[] args) {
      int[] arr = {1, 2, 3, 4, 5};
      permutation(arr, 0, arr.length - 1);
  }

  // 递归实现数组全排列
  public static void permutation(int[] arr, int start, int end) {
      if (start == end) {
          // 输出一组排列
          for (int num : arr) {
              System.out.print(num + " ");
          }
          System.out.println();
      } else {
          for (int i = start; i <= end; i++) {
              // 将当前位置和其他位置交换
              swap(arr, i, start);
              permutation(arr, start + 1, end);
              // 还原当前位置
              swap(arr, i, start);
          }
      }
  }

  // 交换数组中两个位置的元素
  public static void swap(int[] arr, int i, int j) {
      int temp = arr[i];
      arr[i] = arr[j];
      arr[j] = temp;
  }
}

4. 总结

全排列算法是一种基于递归思想的算法，可以将多个元素按照不同的顺序进行排列。在JAVA中，我们可以通过递归实现全排列算法，通过不断将当前位置和其他位置的元素进行交换的方式，得到每一个排列的所有可能性。