通过重复循环 3 个元素来查找排列
Find permutations by repeatedly cycling 3 elements
是否有一种算法可以找到一系列唯一元素的所有可能排列并遵循此规则？
从一个给定的排列中，必须通过恰好循环 3 个元素来找到下一个排列。它们可以是任意三个元素。
有了这样的 3 个循环，将只能找到所有排列的一个子集，但是
应该找到所有可能通过 3 个循环到达的排列，并且在找到所有可到达的排列之前，不应找到相同的排列两次。
这是一个示例输入：
1,2,3,4,5
输出可能是：
3,1,2,4,5
2,3,1,4,5
4,2,1,3,5
3,4,1,2,5
1,3,4,2,5
4,1,3,2,5
2,4,3,1,5
...等等
我尝试生成这样一个序列的众多算法之一如下（对于数组 a 和长度 n）：
print (a)
for i = 0 to n-1
for j = i+1 to n-1
for l = j+2 to n-1
for k = j+1 to l
cycle a[i],a[j],a[k]
print (a)
cycle a[i],a[j],a[k]
print (a)
这会生成上面打印的系列，然后继续：
1,2,3,4,5
.. 这是一个已经输出的排列。到目前为止，我尝试过的寻找下一个 3 周期的任何其他算法都未能找到所有 可达 排列。
有这篇旧论文 V. L. Kompel'makher and V. A. Liskovets. Sequential generation of arrangements by a basis of transpositions.，它表明您可以通过简单的换位生成所有排列，并且每个换位必须将排列的第一个元素与任何其他元素（所谓的星号）交换形状的基础）。例如，对于 S(3) 来说，第一个元素（与元素 1 相对）在每一步中都会被交换。
123->213->312->132->231->321->[123, Hamiltonian cycle!]
还有一种类似的方法 A `Hot Potato' Gray Code for Permutations，它不在付费墙后面。本文的一个重要见解是，即使在每个转置中都必须交换元素 1，仍然可以生成所有排列而不重复（元素 1 在每一步中交换）：
123->213->231->132->312->321->[123, Hamiltonian cycle!]
另一种循环遍历星形基的所有排列的算法是来自 Knuths "The Art of computer programming"，第 "Generating all permutations" 章的算法。算法称为"Ehrlich's swap method"。我并不声称了解那里发生了什么，它只是将算法翻译成 java。对你来说最有趣的部分是这里的那一行：
//swap values to get next permutation:
swap(per,0,b[k]);
在每一步中都有一个换位，并且在每个换位中交换元素[0]（->星形基础）。
import java.util.Arrays;
public class EhrlichPermuter {
//Follows Knuths "The Art of computer programming", Chapter "Generating all permutations", "Ehrlich's swap method".
int n;
int[] c;
int[] b;
int[] per;
boolean done;
void initialize(){
c=new int[n];
b=new int[n];
per=new int[n];
for(int j=0;j<n;j++){
b[j]=j;
per[j]=j;
}
}
EhrlichPermuter(int n){
this.n=n;
initialize();
}
void swap(int[] a, int i, int j){
int h=a[i];a[i]=a[j];a[j]=h;
}
int[] getNextPermut(){
int[] result=Arrays.copyOf(per, per.length);//remember permutation
int k=1;
while(c[k]>=k){
c[k]=0;
k++;
if(k==n){
done=true;
initialize();//we got all permutations so far
return result;//return the last permutation
}
}
c[k]=c[k]+1;
//swap values to get next permutation:
swap(per,0,b[k]);
//flip:
int j=1; k--;
while(j<k){
swap(b,j,k);
j++;
k--;
}
return result;//return remembered permutation
}
}
现在困难的事情已经完成了！
最后一步是：(1a)(1b)形式的任意两个连续的对换可以写成一个三元循环(1ab)。因此，您只需跳过具有负宇称的排列。对于 Hot-Potato 这看起来如下
123 --(213)-->231--(132)-->312--(321)-->[123, Hamiltonian cycle!]
跳过 () 中的排列。
我很确定我没有收到这个问题，因为听起来您已经拥有实现它所需的所有部分，但现在开始吧。无论这听起来是否正确，请发表评论。
我选择了递归方法。循环 3 个元素的每个组合，然后递归处理新的组合。只处理独特的组合。
以下是 LINQPad 中作为 C# 程序实现的代码：
void Main()
{
var unique = new HashSet<string>();
Traverse(unique, "12345");
string.Join(", ", unique).Dump();
}
public static void Traverse(HashSet<string> unique, string digits)
{
if (unique.Contains(digits))
return;
unique.Add(digits);
for (int index1 = 0; index1 < digits.Length; index1++)
for (int index2 = 0; index2 < digits.Length; index2++)
{
if (index2 == index1)
continue;
for (int index3 = 0; index3 < digits.Length; index3++)
{
if (index3 == index1 || index3 == index2)
continue;
var c = digits.ToCharArray();
char temp = c[index1];
c[index1] = c[index2];
c[index2] = c[index3];
c[index3] = temp;
Traverse(unique, new string(c));
}
}
}
输出：
12345, 23145, 31245, 14235, 42135, 21435, 13425, 34125, 41325, 15324, 53124, 31524, 12534, 25134, 51234, 13254, 32154, 21354, 14352, 43152, 31452, 15432, 54132, 41532, 13542, 35142, 51342, 45312, 53412, 34512, 42513, 25413, 54213, 41253, 12453, 24153, 45123, 51423, 14523, 43521, 35421, 54321, 42351, 23451, 34251, 45231, 52431, 24531, 32541, 25341, 53241, 43215, 32415, 24315, 52314, 23514, 35214, 15243, 52143, 21543
构建N-element排列
要通过在同一方向重复旋转 3 个元素来生成 N 个元素的排列，您可以从 3 元素旋转构建一个 4 元素排列，然后是 5-从 4 元素排列开始的元素排列，依此类推，直到到达 N 个元素。
例如3元旋转如下：
012
<<< 120
<<< 201
4 元素排列重复使用 3 元素旋转，交替使用旋转第 4 个元素的旋转：
0123
<<< 1203
<<< 2013
<<=< 0312
<<< 3102
<<< 1032
<<=< 0231
<<< 2301
<<< 3021
=<<< 3210
<<< 2130
<<< 1320
（其中 < 是旋转的元素的位置，= 是保持原位的元素的位置。）
5 元素排列重复 4 元素排列，交替旋转第 5 个元素：
01234 <=<=< 23401 <=<=< 40123 <=<=< 12340 <=<=< 34012
<<< 12034 <<< 34201 <<< 01423 <<< 23140 <<< 40312
<<< 20134 <<< 42301 <<< 14023 <<< 31240 <<< 03412
<<=< 03124 <<=< 20341 <<=< 42013 <<=< 14230 <<=< 31402
<<< 31024 <<< 03241 <<< 20413 <<< 42130 <<< 14302
<<< 10324 <<< 32041 <<< 04213 <<< 21430 <<< 43102
<<=< 02314 <<=< 24031 <<=< 41203 <<=< 13420 <<=< 30142
<<< 23014 <<< 40231 <<< 12403 <<< 34120 <<< 01342
<<< 30214 <<< 02431 <<< 24103 <<< 41320 <<< 13042
=<<< 32104 =<<< 04321 =<<< 21043 =<<< 43210 =<<< 10432
<<< 21304 <<< 43021 <<< 10243 <<< 32410 <<< 04132
<<< 13204 <<< 30421 <<< 02143 <<< 24310 <<< 41032
定义 N-element 排列
对于从 N-1 到 N 个元素的每一步，都有多个选项，每个选项都有自己的 end-state。因此，每一步都由 N-1 次旋转定义，它们一起定义了一个 N-element 排列；例如对于上面的例子：
3 ELEMENTS
rotations: <<< <<<
complete permutation: 012 -> 201
4 ELEMENTS
rotations: <<=< <<=< =<<<
complete permutation: 0123 -> 1320
5 ELEMENTS
rotations: <=<=< <=<=< <=<=< <=<=<
complete permutation: 01234 -> 41032
选择旋转
您会在上面的示例中看到，4 元素排列不使用 3 个相同的旋转，而是 <<=<，再次 <<=<，最后 =<<<；这是因为并非所有可能的旋转组合都会产生正确的排列。
要查找可用于 N-element 排列的旋转，请查看 N-1 元素排列的 end-state，并查看它包含哪些循环，例如：
排列0123 -> 1320有两个循环：[031]和[2]，因为位置0移动到位置3，位置3移动到位置1，位置1移动到位置0，而位置 2 保持原位。
排列0123 -> 3210有两个循环：[03]和[12]，因为0和3调换位置，1和2调换位置。
案例：多次循环
要从 N-1 元素排列创建 N-element 排列，您需要使用 N-th 元素旋转前 N-1 个元素中的两个元素。检查N-1元素排列有哪些循环，select旋转点在位置0，在第二个循环的位置。重复此旋转次数与第二个循环中的元素一样多，然后将第二个点移动到第三个循环中的位置（如果有的话），并重复此循环与第三个循环中的元素一样多的次数，并且很快。使用完所有循环后，根据需要重复最后一次旋转。
举个例子会更清楚：
N-1-permutation: 012345 -> 254301
cycles: [042], [15], [3]
0123456 ... 2543016
<<====< 5643012 ... 4103562 (positions 0 and 1, for cycle [15])
<<====< 1203564 ... 0653124 (repeat for second element in [15])
<==<==< 3654120 ... 5214360 (positions 0 and 3, for cycle [3])
<==<==< 4210365 ... 1630425 (done; repeat last rotation till end)
<==<==< 0635421 ... 3245061
<==<==< 5241063 ... 4601523
您会注意到，在 2 个周期的情况下，旋转始终保持不变：
N-1-permutation: 012345 -> 354201
cycles: [0423], [15]
0123456 ... 3542016
<<====< 5642013 ... 2104563 (positions 0 and 1, for cycle [15])
<<====< 1304562 ... 4650132 (repeat for second element in [15])
<<====< 6250134 ... 0315624 (done; repeat last rotation till end)
<<====< 3415620 ... 5261340
<<====< 2061345 ... 1436205
<<====< 4536201 ... 6023451
案例：一个周期
求两个位置X和Y，其中X在Y的左边，N-1排列将X移动到Y，Y不在N-1排列中的right-most位置。然后用第N个元素重复旋转位置X和Y，最后一步旋转Y和right-most位置。
同样，举个例子会让这个更清楚：
N-1-permutation: 012345 -> 153024
cycles: [032451]
positions X and Y: e.g. 0 and 3, because 0 moves to 3 and 3 < 5 (other option: 2 and 4)
0123456 ... 1530246
<==<==< 0536241 ... 5460321 (positions X and Y)
<==<==< 0461325 ... 4210635 (repeat until penultimate rotation)
<==<==< 0215634 ... 2350164
<==<==< 0354162 ... 3640512
<==<==< 0642513 ... 6120453
===<=<< 6125430 ... 1356240 (last rotation: position Y and right-most)
当 N-1 排列由与旋转相同方向的 1 个位置移动组成时，存在一种边缘情况；在这种情况下，在位置 0 和 1 与位置 1 和 2 之间交替：
N-1-permutation: 012345 -> 123450
cycles: [054321]
0123456 ... 1234506
<<====< 2634501 ... 6345021
=<<===< 6415023 ... 4150263
<<====< 1350264 ... 3502614
=<<===< 3042615 ... 0426135
<<====< 4526130 ... 5261340
=<<===< 5601342 ... 6013452
旋转示例selection
这是最多 10 个元素的排列示例；有很多选项，但这个显示了一个有趣的重复模式，从 7 个元素开始（比较用于 7 和 9 元素以及 8 和 10 元素的旋转，以及 7 和 9 元素的结束状态）：
THREE ELEMENTS (3 permutations)
012
<<< 120
<<< 201 = 1 cycle: [012] X=0, Y=1
FOUR ELEMENTS (12 permutations)
0123 ... 2013
<<=< 0312 ... 1032
<<=< 0231 ... 3021
=<<< 3210 ... 1320 = 2 cycles: [031][2] X=0, Y=2
FIVE ELEMENTS (60 permutations)
01234 ... 13204
<=<=< 23401 ... 30421
<=<=< 40123 ... 02143
<=<=< 12340 ... 24310
<=<=< 34012 ... 41032 = 3 cycles: [024][1][3] X=0, Y=1,3
SIX ELEMENTS (360 permutations)
012345 ... 410325
<<===< 150324 ... 251304
<==<=< 351402 ... 053412
<==<=< 453210 ... 154230
<==<=< 254031 ... 352041
<==<=< 052143 ... 450123 = 2 cycles: [024][135] X=0, Y=1
SEVEN ELEMENTS (2,520 permutations)
0123456 ... 4501236
<<====< 5601234 ... 2356014
<<====< 3456012 ... 0134562
<<====< 1234560 ... 5612340
<<====< 6012345 ... 3460125
<<====< 4560123 ... 1245603
<<====< 2345601 ... 6023451 = 5 cycles: [016][2][3][4][5]; X=0, Y=2,3,4,5
EIGHT ELEMENTS (20,160 permutations)
01234567 ... 60234517
<=<====< 20734516 ... 12734506
<==<===< 32764501 ... 03764521
<===<==< 43761520 ... 24761530
<====<=< 54761032 ... 35761042
<====<=< 05761243 ... 40761253
<====<=< 20761354 ... 52761304
<====<=< 32761405 ... 03761425 = 2 cycles: [0][1457263]; X=0, Y=1
NINE ELEMENTS (181,440 permutations)
012345678 ... 037614258
<<======< 387614250 ... 365281740
<<======< 605281743 ... 624708513
<<======< 234708516 ... 271530486
<<======< 761530482 ... 758463102
<<======< 528463107 ... 540126837
<<======< 470126835 ... 413872065
<<======< 153872064 ... 186057324
<<======< 846057321 ... 802345671 = 7 cycles: [018][2][3][4][5][6][7]; X=0, Y=2,3,4,5,6,7
TEN ELEMENTS (1,814,400 permutations)
0123456789 ... 8023456719
<=<======< 2093456718 ... 1293456708
<==<=====< 3298456701 ... 0398456721
<===<====< 4398156720 ... 2498156730
<====<===< 5498106732 ... 3598106742
<=====<==< 6598102743 ... 4698102753
<======<=< 7698102354 ... 5798102364
<======<=< 3798102465 ... 6398102475
<======<=< 4398102576 ... 7498102536
<======<=< 5498102637 ... 3598102647 = 2 cycles: [051483][2679]; X=0, Y=2
生成排列
生成排列的方法是先 select 确定要使用的旋转，然后使用以下顺序执行旋转，其中每三个 3 被 4 替换，每四个 4 被 a 替换5，每五个 5 被 6 代替，依此类推：
3,3,4,3,3,4,3,3,4,3,3,5,3,3,4,3,3,4,3,3,4,3,3,5,3,3,4,3,3,4,3,3,4,3,3,5,3,3,4,3,3,4,3,3,4,3,3,5,3,3,4,3,3,4,3,3,4,3,3,6...
这类似于埃利希序列，因为您可以使用前 2 个旋转生成 3 个元素的 3 个排列，或前 11 个用于 4 个元素的 12 个排列，或前 59 个用于 60 个排列5 个元素，或者一般来说：N!/2-1 次旋转以生成 N!/2 个排列。
（更新：关于实现，请参阅我对这个问题的其他回答。）
无法到达的排列
如问题和评论中所述，使用 3 元素旋转只能生成一半可能的排列。用上述方法生成的每个排列都有一个不可达的伴随排列，可以通过交换前两个元素来创建，例如：
0123 (1023)
<<< 1203 (2103)
<<< 2013 (0213)
<<=< 0312 (3012)
<<< 3102 (1302)
<<< 1032 (0132)
<<=< 0231 (2031)
<<< 2301 (3201)
<<< 3021 (0321)
=<<< 3210 (2310)
<<< 2130 (1230)
<<< 1320 (3120)
在我之前对这个问题的回答中，我描述了一种找到同向 3 元素旋转序列的方法，该序列将生成 N 元素的所有（可达）排列。下面的实现中使用了我能找到的使用此方法的最简单序列。每个元素数量的旋转显示重复模式，仅 N 的 odd/even 值不同；这意味着可以为任意数量的元素轻松生成旋转序列。
N=3: (0,1,2) (0,1,2)
N=4: (0,1,3) (1,2,3) (1,2,3)
N=5: (0,3,4) (0,3,4) (0,3,4) (0,3,4)
N=6: (0,1,5) (0,2,5) (0,2,5) (0,2,5) (0,2,5)
N=7: (0,5,6) (0,5,6) (0,5,6) (0,5,6) (0,5,6) (0,5,6)
N=8: (0,1,7) (0,2,7) (0,3,7) (0,4,7) (0,4,7) (0,4,7) (0,4,7)
...
从 5 个元素开始，您会发现这个重复出现的模式：
N=odd: (0,N-2,N-1) (0,N-2,N-1) (0,N-2,N-1) ...
N=even: (0,1,N-1) (0,2,N-1) (0,3,N-1) ... (0,N-4,N-1) (0,N-4,N-1) (0,N-4,N-1) (0,N-4,N-1)
或者图形化，<表示旋转元素的位置：
N=3 N=4 N=5 N=6 N=7 N=8 N=9 N=10 N=11 N=12
<<< <<=< <==<< <<===< <====<< <<=====< <======<< <<=======< <========<< <<=========<
<<< =<<< <==<< <=<==< <====<< <=<====< <======<< <=<======< <========<< <=<========<
=<<< <==<< <=<==< <====<< <==<===< <======<< <==<=====< <========<< <==<=======<
<==<< <=<==< <====<< <===<==< <======<< <===<====< <========<< <===<======<
<=<==< <====<< <===<==< <======<< <====<===< <========<< <====<=====<
<====<< <===<==< <======<< <=====<==< <========<< <=====<====<
<===<==< <======<< <=====<==< <========<< <======<===<
<======<< <=====<==< <========<< <=======<==<
<=====<==< <========<< <=======<==<
<========<< <=======<==<
<=======<==<
然后 运行 通过按此顺序的旋转序列生成排列，其中每个第 n 个 n 被 替换n+1 :
3,3,4,3,3,4,3,3,4,3,3,5,3,3,4,3,3,4,3,3,4,3,3,5,3,3,4,3,3,4,3,3,4,3,3,5,3,3,4,3,3,4,3,3,4,3,3,5,3,3,4,3,3,4,3,3,4,3,3,6, ...
所以旋转是：
(0,1,2), (0,1,2), (0,1,3), (0,1,2), (0,1,2), (1,2,3), (0,1,2), (0,1,2), (1,2,3), (0,1,2), (0,1,2), (0,3,4),
(0,1,2), (0,1,2), (0,1,3), (0,1,2), (0,1,2), (1,2,3), (0,1,2), (0,1,2), (1,2,3), (0,1,2), (0,1,2), (0,3,4),
(0,1,2), (0,1,2), (0,1,3), (0,1,2), (0,1,2), (1,2,3), (0,1,2), (0,1,2), (1,2,3), (0,1,2), (0,1,2), (0,3,4),
(0,1,2), (0,1,2), (0,1,3), (0,1,2), (0,1,2), (1,2,3), (0,1,2), (0,1,2), (1,2,3), (0,1,2), (0,1,2), (0,3,4),
(0,1,2), (0,1,2), (0,1,3), (0,1,2), (0,1,2), (1,2,3), (0,1,2), (0,1,2), (1,2,3), (0,1,2), (0,1,2), (0,1,5), ...
下面的代码示例生成旋转序列直至达到请求的元素数，然后执行旋转并输出生成的排列。
function rotate3permute(elems) {
// GENERATE ROTATION SEQUENCES
var pos = [,,,[[0,1],[0,1]],[[0,1],[1,2],[1,2]]];
for (var i = 5; i <= elems; i++) {
pos[i] = [];
for (var j = 1; j < i; j++) pos[i].push([0, i % 2 ? i - 2 : j < i - 4 ? j : i - 4])
}
// PREPARE INITIAL PERMUTATION AND STEP COUNTER
var perm = [0,1], step = [,,,], seq = 3;
for (var i = 2; i < elems; i++) {
perm.push(i);
step.push(0);
}
document.write(perm + "<BR>");
// EXECUTE ROTATIONS
while (seq <= elems) {
rotate(pos[seq][step[seq]++], seq - 1);
document.write(perm + "<BR>");
seq = 3;
while (step[seq] == seq - 1) step[seq++] = 0; // seq = 3,3,4,3,3,4,3,3,4,3,3,5...
}
function rotate(pair, third) {
var temp = perm[pair[0]];
perm[pair[0]] = perm[pair[1]];
perm[pair[1]] = perm[third];
perm[third] = temp;
}
}
rotate3permute(8);
注意：在更严格的语言中将 while (step[seq] == seq - 1) 替换为 while (seq <= elems && step[seq] == seq - 1)，以避免数组越界错误。
如前所述，要生成所有排列，而不仅仅是 3 元素旋转可以达到的一半，输出每个排列两次，一次按原样，一次交换前两个元素。
是否有一种算法可以找到一系列唯一元素的所有可能排列并遵循此规则？
从一个给定的排列中，必须通过恰好循环 3 个元素来找到下一个排列。它们可以是任意三个元素。
有了这样的 3 个循环，将只能找到所有排列的一个子集，但是 应该找到所有可能通过 3 个循环到达的排列，并且在找到所有可到达的排列之前，不应找到相同的排列两次。
这是一个示例输入：
1,2,3,4,5
输出可能是：
3,1,2,4,5
2,3,1,4,5
4,2,1,3,5
3,4,1,2,5
1,3,4,2,5
4,1,3,2,5
2,4,3,1,5
...等等
我尝试生成这样一个序列的众多算法之一如下（对于数组 a 和长度 n）：
print (a)
for i = 0 to n-1
for j = i+1 to n-1
for l = j+2 to n-1
for k = j+1 to l
cycle a[i],a[j],a[k]
print (a)
cycle a[i],a[j],a[k]
print (a)
这会生成上面打印的系列，然后继续：
1,2,3,4,5
.. 这是一个已经输出的排列。到目前为止，我尝试过的寻找下一个 3 周期的任何其他算法都未能找到所有 可达 排列。
有这篇旧论文 V. L. Kompel'makher and V. A. Liskovets. Sequential generation of arrangements by a basis of transpositions.，它表明您可以通过简单的换位生成所有排列，并且每个换位必须将排列的第一个元素与任何其他元素（所谓的星号）交换形状的基础）。例如，对于 S(3) 来说，第一个元素（与元素 1 相对）在每一步中都会被交换。
123->213->312->132->231->321->[123, Hamiltonian cycle!]
还有一种类似的方法 A `Hot Potato' Gray Code for Permutations，它不在付费墙后面。本文的一个重要见解是，即使在每个转置中都必须交换元素 1，仍然可以生成所有排列而不重复（元素 1 在每一步中交换）：
123->213->231->132->312->321->[123, Hamiltonian cycle!]
另一种循环遍历星形基的所有排列的算法是来自 Knuths "The Art of computer programming"，第 "Generating all permutations" 章的算法。算法称为"Ehrlich's swap method"。我并不声称了解那里发生了什么，它只是将算法翻译成 java。对你来说最有趣的部分是这里的那一行：
//swap values to get next permutation:
swap(per,0,b[k]);
在每一步中都有一个换位，并且在每个换位中交换元素[0]（->星形基础）。
import java.util.Arrays;
public class EhrlichPermuter {
//Follows Knuths "The Art of computer programming", Chapter "Generating all permutations", "Ehrlich's swap method".
int n;
int[] c;
int[] b;
int[] per;
boolean done;
void initialize(){
c=new int[n];
b=new int[n];
per=new int[n];
for(int j=0;j<n;j++){
b[j]=j;
per[j]=j;
}
}
EhrlichPermuter(int n){
this.n=n;
initialize();
}
void swap(int[] a, int i, int j){
int h=a[i];a[i]=a[j];a[j]=h;
}
int[] getNextPermut(){
int[] result=Arrays.copyOf(per, per.length);//remember permutation
int k=1;
while(c[k]>=k){
c[k]=0;
k++;
if(k==n){
done=true;
initialize();//we got all permutations so far
return result;//return the last permutation
}
}
c[k]=c[k]+1;
//swap values to get next permutation:
swap(per,0,b[k]);
//flip:
int j=1; k--;
while(j<k){
swap(b,j,k);
j++;
k--;
}
return result;//return remembered permutation
}
}
现在困难的事情已经完成了！
最后一步是：(1a)(1b)形式的任意两个连续的对换可以写成一个三元循环(1ab)。因此，您只需跳过具有负宇称的排列。对于 Hot-Potato 这看起来如下
123 --(213)-->231--(132)-->312--(321)-->[123, Hamiltonian cycle!]
跳过 () 中的排列。
我很确定我没有收到这个问题，因为听起来您已经拥有实现它所需的所有部分，但现在开始吧。无论这听起来是否正确，请发表评论。
我选择了递归方法。循环 3 个元素的每个组合，然后递归处理新的组合。只处理独特的组合。
以下是 LINQPad 中作为 C# 程序实现的代码：
void Main()
{
var unique = new HashSet<string>();
Traverse(unique, "12345");
string.Join(", ", unique).Dump();
}
public static void Traverse(HashSet<string> unique, string digits)
{
if (unique.Contains(digits))
return;
unique.Add(digits);
for (int index1 = 0; index1 < digits.Length; index1++)
for (int index2 = 0; index2 < digits.Length; index2++)
{
if (index2 == index1)
continue;
for (int index3 = 0; index3 < digits.Length; index3++)
{
if (index3 == index1 || index3 == index2)
continue;
var c = digits.ToCharArray();
char temp = c[index1];
c[index1] = c[index2];
c[index2] = c[index3];
c[index3] = temp;
Traverse(unique, new string(c));
}
}
}
输出：
12345, 23145, 31245, 14235, 42135, 21435, 13425, 34125, 41325, 15324, 53124, 31524, 12534, 25134, 51234, 13254, 32154, 21354, 14352, 43152, 31452, 15432, 54132, 41532, 13542, 35142, 51342, 45312, 53412, 34512, 42513, 25413, 54213, 41253, 12453, 24153, 45123, 51423, 14523, 43521, 35421, 54321, 42351, 23451, 34251, 45231, 52431, 24531, 32541, 25341, 53241, 43215, 32415, 24315, 52314, 23514, 35214, 15243, 52143, 21543
构建N-element排列
要通过在同一方向重复旋转 3 个元素来生成 N 个元素的排列，您可以从 3 元素旋转构建一个 4 元素排列，然后是 5-从 4 元素排列开始的元素排列，依此类推，直到到达 N 个元素。
例如3元旋转如下：
012
<<< 120
<<< 201
4 元素排列重复使用 3 元素旋转，交替使用旋转第 4 个元素的旋转：
0123
<<< 1203
<<< 2013
<<=< 0312
<<< 3102
<<< 1032
<<=< 0231
<<< 2301
<<< 3021
=<<< 3210
<<< 2130
<<< 1320
（其中 < 是旋转的元素的位置，= 是保持原位的元素的位置。）
5 元素排列重复 4 元素排列，交替旋转第 5 个元素：
01234 <=<=< 23401 <=<=< 40123 <=<=< 12340 <=<=< 34012
<<< 12034 <<< 34201 <<< 01423 <<< 23140 <<< 40312
<<< 20134 <<< 42301 <<< 14023 <<< 31240 <<< 03412
<<=< 03124 <<=< 20341 <<=< 42013 <<=< 14230 <<=< 31402
<<< 31024 <<< 03241 <<< 20413 <<< 42130 <<< 14302
<<< 10324 <<< 32041 <<< 04213 <<< 21430 <<< 43102
<<=< 02314 <<=< 24031 <<=< 41203 <<=< 13420 <<=< 30142
<<< 23014 <<< 40231 <<< 12403 <<< 34120 <<< 01342
<<< 30214 <<< 02431 <<< 24103 <<< 41320 <<< 13042
=<<< 32104 =<<< 04321 =<<< 21043 =<<< 43210 =<<< 10432
<<< 21304 <<< 43021 <<< 10243 <<< 32410 <<< 04132
<<< 13204 <<< 30421 <<< 02143 <<< 24310 <<< 41032
定义 N-element 排列
对于从 N-1 到 N 个元素的每一步，都有多个选项，每个选项都有自己的 end-state。因此，每一步都由 N-1 次旋转定义，它们一起定义了一个 N-element 排列；例如对于上面的例子：
3 ELEMENTS
rotations: <<< <<<
complete permutation: 012 -> 201
4 ELEMENTS
rotations: <<=< <<=< =<<<
complete permutation: 0123 -> 1320
5 ELEMENTS
rotations: <=<=< <=<=< <=<=< <=<=<
complete permutation: 01234 -> 41032
选择旋转
您会在上面的示例中看到，4 元素排列不使用 3 个相同的旋转，而是 <<=<，再次 <<=<，最后 =<<<；这是因为并非所有可能的旋转组合都会产生正确的排列。
要查找可用于 N-element 排列的旋转，请查看 N-1 元素排列的 end-state，并查看它包含哪些循环，例如：
排列0123 -> 1320有两个循环：[031]和[2]，因为位置0移动到位置3，位置3移动到位置1，位置1移动到位置0，而位置 2 保持原位。
排列0123 -> 3210有两个循环：[03]和[12]，因为0和3调换位置，1和2调换位置。
案例：多次循环
要从 N-1 元素排列创建 N-element 排列，您需要使用 N-th 元素旋转前 N-1 个元素中的两个元素。检查N-1元素排列有哪些循环，select旋转点在位置0，在第二个循环的位置。重复此旋转次数与第二个循环中的元素一样多，然后将第二个点移动到第三个循环中的位置（如果有的话），并重复此循环与第三个循环中的元素一样多的次数，并且很快。使用完所有循环后，根据需要重复最后一次旋转。
举个例子会更清楚：
N-1-permutation: 012345 -> 254301
cycles: [042], [15], [3]
0123456 ... 2543016
<<====< 5643012 ... 4103562 (positions 0 and 1, for cycle [15])
<<====< 1203564 ... 0653124 (repeat for second element in [15])
<==<==< 3654120 ... 5214360 (positions 0 and 3, for cycle [3])
<==<==< 4210365 ... 1630425 (done; repeat last rotation till end)
<==<==< 0635421 ... 3245061
<==<==< 5241063 ... 4601523
您会注意到，在 2 个周期的情况下，旋转始终保持不变：
N-1-permutation: 012345 -> 354201
cycles: [0423], [15]
0123456 ... 3542016
<<====< 5642013 ... 2104563 (positions 0 and 1, for cycle [15])
<<====< 1304562 ... 4650132 (repeat for second element in [15])
<<====< 6250134 ... 0315624 (done; repeat last rotation till end)
<<====< 3415620 ... 5261340
<<====< 2061345 ... 1436205
<<====< 4536201 ... 6023451
案例：一个周期
求两个位置X和Y，其中X在Y的左边，N-1排列将X移动到Y，Y不在N-1排列中的right-most位置。然后用第N个元素重复旋转位置X和Y，最后一步旋转Y和right-most位置。
同样，举个例子会让这个更清楚：
N-1-permutation: 012345 -> 153024
cycles: [032451]
positions X and Y: e.g. 0 and 3, because 0 moves to 3 and 3 < 5 (other option: 2 and 4)
0123456 ... 1530246
<==<==< 0536241 ... 5460321 (positions X and Y)
<==<==< 0461325 ... 4210635 (repeat until penultimate rotation)
<==<==< 0215634 ... 2350164
<==<==< 0354162 ... 3640512
<==<==< 0642513 ... 6120453
===<=<< 6125430 ... 1356240 (last rotation: position Y and right-most)
当 N-1 排列由与旋转相同方向的 1 个位置移动组成时，存在一种边缘情况；在这种情况下，在位置 0 和 1 与位置 1 和 2 之间交替：
N-1-permutation: 012345 -> 123450
cycles: [054321]
0123456 ... 1234506
<<====< 2634501 ... 6345021
=<<===< 6415023 ... 4150263
<<====< 1350264 ... 3502614
=<<===< 3042615 ... 0426135
<<====< 4526130 ... 5261340
=<<===< 5601342 ... 6013452
旋转示例selection
这是最多 10 个元素的排列示例；有很多选项，但这个显示了一个有趣的重复模式，从 7 个元素开始（比较用于 7 和 9 元素以及 8 和 10 元素的旋转，以及 7 和 9 元素的结束状态）：
THREE ELEMENTS (3 permutations)
012
<<< 120
<<< 201 = 1 cycle: [012] X=0, Y=1
FOUR ELEMENTS (12 permutations)
0123 ... 2013
<<=< 0312 ... 1032
<<=< 0231 ... 3021
=<<< 3210 ... 1320 = 2 cycles: [031][2] X=0, Y=2
FIVE ELEMENTS (60 permutations)
01234 ... 13204
<=<=< 23401 ... 30421
<=<=< 40123 ... 02143
<=<=< 12340 ... 24310
<=<=< 34012 ... 41032 = 3 cycles: [024][1][3] X=0, Y=1,3
SIX ELEMENTS (360 permutations)
012345 ... 410325
<<===< 150324 ... 251304
<==<=< 351402 ... 053412
<==<=< 453210 ... 154230
<==<=< 254031 ... 352041
<==<=< 052143 ... 450123 = 2 cycles: [024][135] X=0, Y=1
SEVEN ELEMENTS (2,520 permutations)
0123456 ... 4501236
<<====< 5601234 ... 2356014
<<====< 3456012 ... 0134562
<<====< 1234560 ... 5612340
<<====< 6012345 ... 3460125
<<====< 4560123 ... 1245603
<<====< 2345601 ... 6023451 = 5 cycles: [016][2][3][4][5]; X=0, Y=2,3,4,5
EIGHT ELEMENTS (20,160 permutations)
01234567 ... 60234517
<=<====< 20734516 ... 12734506
<==<===< 32764501 ... 03764521
<===<==< 43761520 ... 24761530
<====<=< 54761032 ... 35761042
<====<=< 05761243 ... 40761253
<====<=< 20761354 ... 52761304
<====<=< 32761405 ... 03761425 = 2 cycles: [0][1457263]; X=0, Y=1
NINE ELEMENTS (181,440 permutations)
012345678 ... 037614258
<<======< 387614250 ... 365281740
<<======< 605281743 ... 624708513
<<======< 234708516 ... 271530486
<<======< 761530482 ... 758463102
<<======< 528463107 ... 540126837
<<======< 470126835 ... 413872065
<<======< 153872064 ... 186057324
<<======< 846057321 ... 802345671 = 7 cycles: [018][2][3][4][5][6][7]; X=0, Y=2,3,4,5,6,7
TEN ELEMENTS (1,814,400 permutations)
0123456789 ... 8023456719
<=<======< 2093456718 ... 1293456708
<==<=====< 3298456701 ... 0398456721
<===<====< 4398156720 ... 2498156730
<====<===< 5498106732 ... 3598106742
<=====<==< 6598102743 ... 4698102753
<======<=< 7698102354 ... 5798102364
<======<=< 3798102465 ... 6398102475
<======<=< 4398102576 ... 7498102536
<======<=< 5498102637 ... 3598102647 = 2 cycles: [051483][2679]; X=0, Y=2
生成排列
生成排列的方法是先 select 确定要使用的旋转，然后使用以下顺序执行旋转，其中每三个 3 被 4 替换，每四个 4 被 a 替换5，每五个 5 被 6 代替，依此类推：
3,3,4,3,3,4,3,3,4,3,3,5,3,3,4,3,3,4,3,3,4,3,3,5,3,3,4,3,3,4,3,3,4,3,3,5,3,3,4,3,3,4,3,3,4,3,3,5,3,3,4,3,3,4,3,3,4,3,3,6...
这类似于埃利希序列，因为您可以使用前 2 个旋转生成 3 个元素的 3 个排列，或前 11 个用于 4 个元素的 12 个排列，或前 59 个用于 60 个排列5 个元素，或者一般来说：N!/2-1 次旋转以生成 N!/2 个排列。
（更新：关于实现，请参阅我对这个问题的其他回答。）
无法到达的排列
如问题和评论中所述，使用 3 元素旋转只能生成一半可能的排列。用上述方法生成的每个排列都有一个不可达的伴随排列，可以通过交换前两个元素来创建，例如：
0123 (1023)
<<< 1203 (2103)
<<< 2013 (0213)
<<=< 0312 (3012)
<<< 3102 (1302)
<<< 1032 (0132)
<<=< 0231 (2031)
<<< 2301 (3201)
<<< 3021 (0321)
=<<< 3210 (2310)
<<< 2130 (1230)
<<< 1320 (3120)
在我之前对这个问题的回答中，我描述了一种找到同向 3 元素旋转序列的方法，该序列将生成 N 元素的所有（可达）排列。下面的实现中使用了我能找到的使用此方法的最简单序列。每个元素数量的旋转显示重复模式，仅 N 的 odd/even 值不同；这意味着可以为任意数量的元素轻松生成旋转序列。
N=3: (0,1,2) (0,1,2)
N=4: (0,1,3) (1,2,3) (1,2,3)
N=5: (0,3,4) (0,3,4) (0,3,4) (0,3,4)
N=6: (0,1,5) (0,2,5) (0,2,5) (0,2,5) (0,2,5)
N=7: (0,5,6) (0,5,6) (0,5,6) (0,5,6) (0,5,6) (0,5,6)
N=8: (0,1,7) (0,2,7) (0,3,7) (0,4,7) (0,4,7) (0,4,7) (0,4,7)
...
从 5 个元素开始，您会发现这个重复出现的模式：
N=odd: (0,N-2,N-1) (0,N-2,N-1) (0,N-2,N-1) ...
N=even: (0,1,N-1) (0,2,N-1) (0,3,N-1) ... (0,N-4,N-1) (0,N-4,N-1) (0,N-4,N-1) (0,N-4,N-1)
或者图形化，<表示旋转元素的位置：
N=3 N=4 N=5 N=6 N=7 N=8 N=9 N=10 N=11 N=12
<<< <<=< <==<< <<===< <====<< <<=====< <======<< <<=======< <========<< <<=========<
<<< =<<< <==<< <=<==< <====<< <=<====< <======<< <=<======< <========<< <=<========<
=<<< <==<< <=<==< <====<< <==<===< <======<< <==<=====< <========<< <==<=======<
<==<< <=<==< <====<< <===<==< <======<< <===<====< <========<< <===<======<
<=<==< <====<< <===<==< <======<< <====<===< <========<< <====<=====<
<====<< <===<==< <======<< <=====<==< <========<< <=====<====<
<===<==< <======<< <=====<==< <========<< <======<===<
<======<< <=====<==< <========<< <=======<==<
<=====<==< <========<< <=======<==<
<========<< <=======<==<
<=======<==<
然后 运行 通过按此顺序的旋转序列生成排列，其中每个第 n 个 n 被 替换n+1 :
3,3,4,3,3,4,3,3,4,3,3,5,3,3,4,3,3,4,3,3,4,3,3,5,3,3,4,3,3,4,3,3,4,3,3,5,3,3,4,3,3,4,3,3,4,3,3,5,3,3,4,3,3,4,3,3,4,3,3,6, ...
所以旋转是：
(0,1,2), (0,1,2), (0,1,3), (0,1,2), (0,1,2), (1,2,3), (0,1,2), (0,1,2), (1,2,3), (0,1,2), (0,1,2), (0,3,4),
(0,1,2), (0,1,2), (0,1,3), (0,1,2), (0,1,2), (1,2,3), (0,1,2), (0,1,2), (1,2,3), (0,1,2), (0,1,2), (0,3,4),
(0,1,2), (0,1,2), (0,1,3), (0,1,2), (0,1,2), (1,2,3), (0,1,2), (0,1,2), (1,2,3), (0,1,2), (0,1,2), (0,3,4),
(0,1,2), (0,1,2), (0,1,3), (0,1,2), (0,1,2), (1,2,3), (0,1,2), (0,1,2), (1,2,3), (0,1,2), (0,1,2), (0,3,4),
(0,1,2), (0,1,2), (0,1,3), (0,1,2), (0,1,2), (1,2,3), (0,1,2), (0,1,2), (1,2,3), (0,1,2), (0,1,2), (0,1,5), ...
下面的代码示例生成旋转序列直至达到请求的元素数，然后执行旋转并输出生成的排列。
function rotate3permute(elems) {
// GENERATE ROTATION SEQUENCES
var pos = [,,,[[0,1],[0,1]],[[0,1],[1,2],[1,2]]];
for (var i = 5; i <= elems; i++) {
pos[i] = [];
for (var j = 1; j < i; j++) pos[i].push([0, i % 2 ? i - 2 : j < i - 4 ? j : i - 4])
}
// PREPARE INITIAL PERMUTATION AND STEP COUNTER
var perm = [0,1], step = [,,,], seq = 3;
for (var i = 2; i < elems; i++) {
perm.push(i);
step.push(0);
}
document.write(perm + "<BR>");
// EXECUTE ROTATIONS
while (seq <= elems) {
rotate(pos[seq][step[seq]++], seq - 1);
document.write(perm + "<BR>");
seq = 3;
while (step[seq] == seq - 1) step[seq++] = 0; // seq = 3,3,4,3,3,4,3,3,4,3,3,5...
}
function rotate(pair, third) {
var temp = perm[pair[0]];
perm[pair[0]] = perm[pair[1]];
perm[pair[1]] = perm[third];
perm[third] = temp;
}
}
rotate3permute(8);
注意：在更严格的语言中将 while (step[seq] == seq - 1) 替换为 while (seq <= elems && step[seq] == seq - 1)，以避免数组越界错误。
如前所述，要生成所有排列，而不仅仅是 3 元素旋转可以达到的一半，输出每个排列两次，一次按原样，一次交换前两个元素。