全排列

发表于 | 分类于

问题

生成n个元素的所有排列对象

递归生成

这里我先把代码贴出来，结合代码和下面的解释会更容易理解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public void swap(int arr[],int a,int b){
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}
public void sort(int arr[],int len,int n){
    if (len==n){
        for (int i=0;i<=n;i++){
            System.out.print(arr[i]+" ");
        }
        System.out.println();
    }else {
        for (int i=len;i<=n;i++){
            swap(arr,len,i);
            sort(arr,len+1,n);
            swap(arr,len,i);
        }
    }
}

这里说明一点，用java不方便的一点是，不能用引用，所以不得不将swap写成上面那样。 举例：{1,2,3,4}
当是以1开头时：

  • (1).首元素不动，对大括号内的元素进行全排列
    1,{2,3,4}
  • (2).大括号内的首元素不动，对中括号内的元素进行全排列。
    1,{2,[3,4]}
  • (3).中括号内的元素的首元素不动，对小括号内的元素全排列，而小括号内只剩一个元素，就是它的所有情况。
    1,{2,[3,(4)]}
    所以第一种组合为(1,2,3,4)。
    此时，以1,2,3开头的结果列举完了。
  • (4).交换下标为2,3的值(注：这里是下标，不是值，且下标从零开始)，重复(2),(3)步骤。
    得出第二种组合(1,2,4,3)(注：每次交换位置后，将结果输出后需要将位置换回来)。此时，以1,2开头的情况列举完了;
  • (5).交换下标为1,2的值，重复步骤(2),(3),(4)。
    得到两种组合，(1,3,2,4)和(1,3,4,2)。此时，以1,3开头的情况列举完了;
  • (6).交换下标为1,3的值，重复步骤(2),(3),(4)。
    得到两种组合，(1,4,3,2)和(1,4,2,3);
    此时，以1,4开头的情况列举完了，这时其实以1开头的所有情况列举完了。
  • (7).交换下标为0,1的值，重复步骤(1),(2),(3),(4),(5),(6)。 得到六种组合(2,1,3,4),(2,1,4,3),(2,3,1,4),(2,3,4,1),(2,4,3,1),(2,4,1,3);
  • (8).交换下标为0,2的值，重复步骤(1),(2),(3),(4),(5),(6)。
    得到六种组合(3,2,1,4),(3,2,4,1),(3,1,2,4),(3,1,4,2),(3,4,1,2),(3,4,2,1);
  • (9).交换下标为0,3的值，重复步骤(1),(2),(3),(4),(5),(6)。
    得到六种组合(4,2,3,1),(4,2,1,3),(4,3,2,1),(4,3,1,2),(4,1,3,2),(4,1,2,3);
    至此得到所有种可能。