全排列算法【java实现】

    之前用的都是组合比较多，对于一些全排列算法以及组合算法，递归是无法满足我们的，效率不高；

在网上浏览了一些帖子，有一种算法思想我觉得可取，下面是我用JAVA实现的测试代码(可执行):

package Demon;

public class Main {

public static void main(String[] args) {

        //全排列算法测试

        int[] arr = new int[]{1,2,3,4};

        for(int i :arr)

        {

        System.out.print(i + " ");

        }

        System.out.println();

        int totalnum = 1;

        while(NextNumber(arr,arr.length))

        {

        for(int i :arr)

            {

            System.out.print(i + " ");

            }

            System.out.println();

            totalnum ++;

        }

        System.out.println("Total Num: " + totalnum);

}

private static Boolean NextNumber(int[] arr, int n)

{

//数组最后一个元素位置

int lastIndex = n-1;

//从右向左确定第一个数字（前面的数字比它小）

int firstIndex = lastIndex;

for(;arr[firstIndex-1]>arr[firstIndex];firstIndex--)

{

if(firstIndex == 1)

{

//已经轮询完毕,此数已经是最大的那个数

return false;

}

}

//从右向左确定一个交换数（此数比arr[firstIndex]小且比arr[firstIndex-1]大）

int swapIndex = lastIndex;

for(;swapIndex > firstIndex;swapIndex--)

{

if(arr[swapIndex] < arr[firstIndex] && arr[swapIndex] > arr[firstIndex-1])

{

break;

}

}

//交换数字

swap(arr,firstIndex-1,swapIndex);

//将firstIndex右边的数字排序

for(;firstIndex < lastIndex;firstIndex++,lastIndex--)

{

if(arr[firstIndex] > arr[lastIndex])

{

swap(arr,firstIndex,lastIndex);

}

}

return true;

}

private static void swap(int[] arr,int i, int j)

{

int tmp = arr[i];

arr[i] = arr[j];

arr[j] = tmp;

}

}

    之前用的都是组合比较多，对于一些全排列算法以及组合算法，递归是无法满足我们的，效率不高；

在网上浏览了一些帖子，有一种算法思想我觉得可取，下面是我用JAVA实现的测试代码(可执行):

package Demon;

public class Main {

public static void main(String[] args) {

        //全排列算法测试

        int[] arr = new int[]{1,2,3,4};

        for(int i :arr)

        {

        System.out.print(i + " ");

        }

        System.out.println();

        int totalnum = 1;

        while(NextNumber(arr,arr.length))

        {

        for(int i :arr)

            {

            System.out.print(i + " ");

            }

            System.out.println();

            totalnum ++;

        }

        System.out.println("Total Num: " + totalnum);

}

private static Boolean NextNumber(int[] arr, int n)

{

//数组最后一个元素位置

int lastIndex = n-1;

//从右向左确定第一个数字（前面的数字比它小）

int firstIndex = lastIndex;

for(;arr[firstIndex-1]>arr[firstIndex];firstIndex--)

{

if(firstIndex == 1)

{

//已经轮询完毕,此数已经是最大的那个数

return false;

}

}

//从右向左确定一个交换数（此数比arr[firstIndex]小且比arr[firstIndex-1]大）

int swapIndex = lastIndex;

for(;swapIndex > firstIndex;swapIndex--)

{

if(arr[swapIndex] < arr[firstIndex] && arr[swapIndex] > arr[firstIndex-1])

{

break;

}

}

//交换数字

swap(arr,firstIndex-1,swapIndex);

//将firstIndex右边的数字排序

for(;firstIndex < lastIndex;firstIndex++,lastIndex--)

{

if(arr[firstIndex] > arr[lastIndex])

{

swap(arr,firstIndex,lastIndex);

}

}

return true;

}

private static void swap(int[] arr,int i, int j)

{

int tmp = arr[i];

arr[i] = arr[j];

arr[j] = tmp;

}

}