Zero Lee的专栏

Generating Permutations

A permutation can be obtained by selecting an element in the given set and recursively permuting the remaining elements.

{ ai,P(a1,...,ai-1,ai+1,...,aN) if N > 1 P(a1,...,aN) = aN if N = 1
--|--|--|-| |a|b-|c-d-| a|------------b------------c-------------d --|--|--|-| ---|-|--|--| ---|--|-|--| --|--|--|-| |-|b-|c-d-| |a-|-|c-|d-| |a-|b-|-|d-| |a|b-|c-|-|

At each stage of the permutation process, the given set of elements consists of two parts: a subset of values that already have been processed, and a subset that still needs to be processed. This logical seperation can be physically realized by exchanging, in the i’th step, the i’th value with the value being chosen at that stage. That approaches leaves the first subset in the first i locations of the outcome.

--|--|--|-| |a|b-|c-d-| --|--|------------|--------------------------|--|-| a||b |c d | |b a |c |d | |c||b |a|d | |d|b |c |a| -----|--------------------------|---- ----------- --|--|--|-| ---|-|--|--| ---|--|-|--| b-|a-|c-d-| |b-|c|a-|d-| |b-|d-|c|a-| ---|--|------------|--|-| |b-|c-a-|d-| b-|c-|d-|a| | b-|c-|d-|a| |-|--|--|-|
 
permute(i) 
   if i == N  output A[N] 
   else 
      for j = i to N do 
         swap(A[i], A[j]) 
         permute(i+1) 
         swap(A[i], A[j]) 

posted on 2011-09-21 15:22 Zero Lee 阅读(252) 评论(0)  编辑 收藏 引用 所属分类: Data structure and algorithms


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理