产生所有排列--字典顺序(非递归解)
编写一个程序,用字典顺序列出n个元素的所有排列(Permutation).
说明:
下面是一个n = 4,用字典顺序列出来的所有排列,一共为4! = 24个。
1234 2134 3124 4123
1243 2143 3142 4132
1324 2314 3214 4213
1342 2341 3241 4231
1423 2413 3412 4312
1432 2431 3421 4321
在产生所有排列–字典顺序中,用了递归的方法求解字典排列,这里使用非递归的方法。据Hall和Knuth的考证,200多年前(1812年)Fischer和Kruse在一本书中就提到了这个方法.
step 1: 从右往左找,找到第一个i使得nums[i] < nums[i + 1]
step 2: 从右往左找,找到第一个j使得nums[i] < nums[j]
step 3: 交换nums[i]与nums[j]
step 4: 将nums[i + 1],…nums[n]反转
在step 1时,如果找不到满足条件的i, 则结束程序。
例如153642,
从右往左找,找到第一个 i = 2 使得nums[i] < nums[i + 1] 即3 < 6
从右往左找,找到第一个 j = 3 使得nums[i] < nums[j] 即 3 < 4
交换nums[i]和nums[j], 得到154632
将nums[i + ],..nums[n]反转,即将632反转,得到154236
所以154236就是153642的下一个排列。
如此从要求12…n的字典排列,可以从12,…n开始,一直用求下一个排列的方法列出所有排列。
1 | package chapter3; |