精华内容
下载资源
问答
  • 字典序全排列

    2017-07-12 19:03:00
    思路:从左向右找到不符合递增规律的第一个数,比如1,2,5,4,3中的这个数就是2,将其与其右面递增序列中的比他大的最小数,比如在前面例子中的3互换,得到1,3,5,4,2,最后,将该数...public class 字典序全排列 { publi

    思路:从左向右找到不符合递增规律的第一个数,比如1,2,5,4,3中的这个数就是2,将其与其右面递增序列中的比他大的最小数,比如在前面例子中的3互换,得到1,3,5,4,2,最后,将该数右边的递增序列排序,得到1,3,2,4,5即可。上面这个是求某一个数的下一个排列,而全排列只需按这个思路,将初始数组设置为从小到大排列的数组即可得到排列。

    public class 字典序全排列 {
    	public static int Min(int array[],int index,int num)
    	{
    		int low=index;
    		for(int i=index+1;i<array.length;i++)
    		{
    			if(array[low]>array[i]&&array[i]>num)
    			{
    				low=i;
    			}
    		}
    		return low;
    	}
    	public static void Permutation(int array[])
    	{
    		boolean judge=true;
    		System.out.println(Arrays.toString(array));
    		while(judge)
    		{			
    			for(int i=array.length-1;i>=1;i--)
    			{
    				if(array[i]>array[i-1])
    				{
    					int low=Min(array,i,array[i-1]);
    					array[i-1]=array[i-1]^array[low];
    					array[low]=array[low]^array[i-1];
    					array[i-1]=array[i-1]^array[low];
    					Arrays.sort(array,i,array.length);
    					System.out.println(Arrays.toString(array));
    					break;
    				}
    				if(i==1)
    				{
    					judge=false;
    				}
    			}
    		}
    	}
    	public static void main(String[] args) {
    		int array[]={1,3,5,7,9};
    		Permutation(array);
    	}
    
    }



    展开全文
  • N个数字的字典序全排列,自己的小作业,参考dfs写的,
  • /***字典序全排列*字符串的全排列*比如单词"too" 它的全排列是"oot","oto","too"*1,从右端开始扫描,若出现前一个比后一个小,记录前一个的元素下表index*2,再找出index以后比该元素大的中的最小值的下标,(实现见 ...

    import java.util.Arrays;

    /**

    *字典序全排列

    *字符串的全排列

    *比如单词"too" 它的全排列是"oot","oto","too"

    *1,从右端开始扫描,若出现前一个比后一个小,记录前一个的元素下表index

    *2,再找出index以后比该元素大的中的最小值的下标,(实现见 下面的getMin方法)

    *3,index以后的元素实现反转(实现 见下面的reverse方法)

    *结束条件:前一个都比后一个大的情况

    */

    public class StringExpress{

    int getMin(char[]input,int index){

    char min=input[index];

    int minIndex=index+1;

    char result='z';

    for(int i=index+1;i

    if(input[i]>min&&input[i]

    result=input[i];

    minIndex=i;

    }

    }

    return minIndex;

    }

    void exchange(char []input,int index,int minIndex){

    char temp=input[index];

    input[index]=input[minIndex];

    input[minIndex]=temp;

    }

    void reverse(char input[],int first,int end) {

    while(first

    exchange(input,first,end);

    first++;

    end--;

    }

    }

    void getDictionary(char c[]){

    System.out.println(new String(c));

    //boolean flag=true;

    int i=0;

    while(true){

    i=c.length-1;

    for(;i>0;i--){

    if(c[i-1]

    }

    if(i==0)break;

    int minIndex=getMin(c,i-1);

    exchange(c,i-1,minIndex);

    reverse(c,i,c.length-1);

    System.out.println(new String(c));

    }

    }

    public static void main(String []args){

    String input="aat";

    char [] c=input.toCharArray();

    Arrays.sort(c);

    new StringExpress().getDictionary(c);

    }

    }

    展开全文
  • python 按字典序全排列递归实现 代码: def swap(num, i, j): for x in range(j, i, -1): tmp = num[x] num[x] = num[x-1] num[x-1] = tmp def swapback(num, i, j): for x in range(i, j): tmp = num[x] ...

    python 按字典序全排列递归实现

    代码:

    def swap(num, i, j):
        for x in range(j, i, -1):
            tmp = num[x]
            num[x] = num[x-1]
            num[x-1] = tmp
    
    def swapback(num, i, j):
        for x in range(i, j):
            tmp = num[x]
            num[x] = num[x+1]
            num[x+1] = tmp
            
    def permutation(numbers, start):
        if start == len(numbers) - 1:
            print(" ".join(numbers))
        else:
            for i in range(start, len(numbers)):
                swap(numbers, start, i)
                permutation(numbers, start + 1)
                swapback(numbers, start, i)
    
    
    def func():
        num = int(input())
        numbers = []
        for i in range(1, num + 1):
            numbers.append(str(i))
        permutation(numbers, 0)
    
        
    if __name__ == "__main__":
        func()
    

    输出结果:

    1 2 3
    1 3 2
    2 1 3
    2 3 1
    3 1 2
    3 2 1

    递归 顺序排列

    递归实现全排列的同时,需要保证能够按照字典序输出。

    起始列表按序保存,在调换位置时,将要调换的值从后往前循环移到start位置而非直接交换两个点的位置,保证后半部分数值能保持大小顺序。

    错误结果示例(如使用简单交换方式)

    1 2 3
    1 3 2
    2 1 3
    2 3 1
    3 2 1
    3 1 2

    展开全文
  • java字典序全排列

    2016-12-12 18:30:00
    *字典序全排列 *字符串的全排列 *比如单词"too" 它的全排列是"oot","oto","too" *1,从右端开始扫描,若出现前一个比后一个小,记录前一个的元素下表index *2,再找出index以后比该元素大的中的最小值的下标,...
    import java.util.Arrays;
    /**
    *字典序全排列
    *字符串的全排列
    *比如单词"too" 它的全排列是"oot","oto","too"
    *1,从右端开始扫描,若出现前一个比后一个小,记录前一个的元素下表index
    *2,再找出index以后比该元素大的中的最小值的下标,(实现见 下面的getMin方法)
    *3,index以后的元素实现反转(实现 见下面的reverse方法)
    *结束条件:前一个都比后一个大的情况
    */
    public class StringExpress{
       int getMin(char[]input,int index){
            char min=input[index];
            int minIndex=index+1;
            char result='z';
            for(int i=index+1;i<input.length;i++){
                  if(input[i]>min&&input[i]<result){
                      result=input[i];
                      minIndex=i;
                  }
            }
            return minIndex;
       }
       void exchange(char []input,int index,int minIndex){
               char temp=input[index];
               input[index]=input[minIndex];
               input[minIndex]=temp;
       }
       void reverse(char input[],int first,int end) {
          while(first<end){
               exchange(input,first,end);
               first++;
               end--;
          }
       }
       void getDictionary(char c[]){
           System.out.println(new String(c));
           //boolean flag=true;
           int i=0;
           while(true){
             i=c.length-1;
              for(;i>0;i--){
                   if(c[i-1]<c[i])break;
              }
              if(i==0)break;
              int minIndex=getMin(c,i-1);
              exchange(c,i-1,minIndex);
              reverse(c,i,c.length-1);
              System.out.println(new String(c));
           }
           
       }
       public static void main(String []args){
        String input="aat";
        char [] c=input.toCharArray();
        Arrays.sort(c);
        new StringExpress().getDictionary(c);
       }
    }
    

     

    转载于:https://www.cnblogs.com/firstdream/p/6165549.html

    展开全文
  • *字典序全排列 *字符串的全排列 *比如单词"too" 它的全排列是"oot","oto","too" *1,从右端开始扫描,若出现前一个比后一个小,记录前一个的元素下表index *2,再找出index以后比该元素大的中的最小值的下标,...
  • 字典序 全排列 (xmu oj) by C++题目描述:题目分析代码截图 题目描述: 描述 Generate the complete permutation of 1…N 输入 Each input file contains only one non-negative integer N (0< N < 9) ...
  • 一、字典序 字典序,就是按照字典中出现的先后顺序进行排序。 1.单个字符 在计算机中,25个字母以及数字字符,字典排序如下: ‘0’ < ‘1’ < ‘2’ < … < ‘9’ < ‘a’ < ‘b’ < … < ...
  • 字典序全排列的求解

    2020-04-03 14:15:49
    字典序输出的全排列,可以理解为某种意义上的“从小到大”排列顺序。 例如:{1,2,3}按字典序全排列为:123,132,213,231,312,321 填数法:它的函数实现可以理解为,将原数组的数,优先选择较小的数,填入新数组中...
  • ACM常用模板 字典序全排列

    千次阅读 2015-09-07 09:57:44
    //字典序全排列与序号的转换 int perm2num(int n,int *p){ int i,j,ret=0,k=1; for (i=n-2;i>=0;k*=n-(i--)) for (j=i+1;j if (p[j] ret+=k; return ret; } void num2perm(int n,int *p,int t){ int i...
  • 字典序全排列简单研究

    千次阅读 2014-06-03 17:00:50
    最近看算法设计与分析基础这本书,里面讲到了一个字典序全排列问题,书中的方法是: (1)从右至左扫描当前的一个排列,需找第一个连续的选择ai和ai+1,使得ai (2)在尾部存在大于ai的最小数也就是min{aj | aj>ai...
  • 字典序全排列算法

    千次阅读 2018-03-08 11:52:52
    在此基础上规定两个全排列的先后是从左到右逐个比较字符的先后顺序[例]字符集{1,2,3},较小的数字较先,这样按字典序生成的全排列是: 123,132,213,231,312,321※ 一个全排列可看做一个字符串,字符串可有前缀、后缀。...
  • package edu.pku.ss.hlj;/*** 字典序法中,对于数字1、2、3......n的排列,不同排列的先后关系是从左到右逐个比较对应的数字的先后来决定的。...* 字典序算法如下:* 设P是1~n的一个全排列:p=p...
  • 生成字典序全排列

    千次阅读 2015-03-27 21:10:39
     有好几种算法可以生成全排列,比如自底向上插入生成全排列、Johnson-Trotter算法生成、字典序生成等等。  我想到用字典序生成全排列的一个算法。  字典序排列就是按照字典a-z,1-9的顺序给出字符串的顺序全排列,...
  • 最近在牛客网上刷题,遇到一道剑指offer上的编程题还蛮有意思的,所以把它记录下来与大家分享,原题如下: ...在网上查了以后发现这是一种特定的算法可以解决的问题,该算法称之为字典序全排列算法: 非递归算法

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,210
精华内容 884
关键字:

字典序全排列