需要注意的是，我手工在纸上进行了数学推导以得出上述证明。我不确定仅使用现代计算机这种媒介是否能够得出这些证明。
下文中，“效率”一词的定义是指在最短时间内完成算法的离散部分或整个算法，无论是在数学上、编程上还是计算上。
在进一步研究如何从原始集合或当前排列生成下一个字典序排列的过程时，重新阅读了@chqrlie在Permutations without recursive function call中的回答后，我试图在纸上写下索引，以观察这些索引之间是否存在任何可以用来执行特定任务的数学关系。
我发现了几个有趣的真相，并在下面证明了它们。
例如，当我们写出以下值时：
a,b,c
或者
abc
或者，相反地编写表示值的索引。
0,1,2
或者
012
既然我们已经知道一个集合，
abc
我们可以通过交换集合中最后两个值或索引来生成下一个字典序排列。
acb
或者
021
我们可以忽略值，这些值可以是任何类型的数据，并专注于使用索引进行检查，因为离散数字更适合相互关联可能的关系，而不是可能无限多的多样化值。
因此，对于原始集的第二个字典索引来说，
abc
我们可以将索引的值表示为数字，并观察。
0,2,1
或者
021
首先需要索引的是
012
第二个是
021
我们知道原始集合的 .length 是 3，如果我们记住原始值集合的 .length，我们就可以删除开头的
0
将索引减少到指定数量的位置
12
并且
21
分别是 0。当下一个操作的结果小于原始集时，可以将 0 作为从原始集引用索引的索引以获取索引 0 处的值。
当我们尝试绘制 12 和 21 之间的潜在关系时，我们发现
21 - 12 = 9
当我们继续时，我们发现下一个词典索引是：
102
减去前面的索引
102 - 21 = 81
其中102是下一个字典序排列，表示为以下数值
bac
这为我们提供了指数之间的常见关系，这些指数用数字表示为九
9
这种关系对于无限数量的以数字表示的输入值是明显且可重复的。我们可以绘制这些关系的图形，这取决于观察者的视角，可以看作两个斜率，当从结果排列集合的第一个值开始绘制图形时，具有倒置的顶点偏移。
// graph 1
0,9,81
// graph 2
abc 012 0
acb 021 1 9
bac 102 2 81
bca 120 3 18
cab 201 4 81
cba 210 5 9
/\/\
/ \
我们可以观察到，在倾斜斜率上的数字与相应的赤纬斜率上的数字是相同的，这是在将可能的排列总数的分数除以一半的倒数后进行的，例如，对于六个排列，我们减去一个，剩下五个，记住我们仍需要奇数索引集，我们使用倒置的顶点处的数字作为枢轴，剩下四个索引，分别称为倾斜和赤纬斜率。
我们可以观察到，在赤纬斜率图中的数字与相应的倾斜斜率图中具有相同y坐标的相邻角度是相同的。
因此，以下我证明了一个无限的置换集合可以通过利用数字九的加法或乘法来计算、生成、过滤和派生一个无限的输入集合。
9
通过匹配仅包括输入数字索引编号的数字，而不在集合中重复，来计算排列数量。
此外，我证明只需要将索引作为斜率数字或者可能的排列总数除以二加一，即可得出给定输入的排列总数。
正如本文前言所强调的那样，这些计算可能没有经过数小时手动计算才得以实现。屏幕无法像纸张一样提供相同的介质；也无法从各个物理维度查看纸张。
使用编程语言表达算法是另一个任务。
以下是使用“JavaScript”编程语言实现的发现、证明和表达的进展。第一个版本具有不准确的RegExp，如 @Tushar 指出的那样，已更正RegExp，尽管不正确的RegExp返回相同结果。
给定输入为数组
var arr = ["a", "b", "c", "d"];
// version 1
function getNextLexicographicPermutation(arr) {
var len = arr.length;
var idx = arr.map(function(_, index) {
return index
});
var re = new RegExp("[" + len + "-9]|(.)(?!=\\1)");
var n = Math.pow(10, len - 1);
var p = 9;
var last = Number(idx.slice().reverse().join(""));
var res = [idx];
var curr = Number(res[res.length - 1].join(""));
while (curr < last) {
for (var prev = curr, next, k; prev <= last; prev += p) {
if ((re.test(prev))) {
k = String(prev);
if (k.length >= len - 1) { // && Math.max.apply(Math, j) < len
next = [];
for (var i = 0; i < k.length; i++) {
if (next.indexOf(Number(k[i])) == -1
&& idx.indexOf(Number(k[i])) !== -1) {
next.push(Number(k[i]))
}
}
if (prev < n && next.length === len - 1
|| next.length === len && prev > curr) {
res[res.length] = next.length < len
? [0].concat.apply([0], next)
: next;
}
}
}
curr = prev;
}
};
return res.map(function(value) {
return value.map(function(index) {
return arr[index]
})
})
}
getNextLexicographicPermutation(arr);
数组 arr 的索引数字之间的数值差异图表如下：
// graph 3
// reflecting input `abcd`
[9,81,18,81,9,702,9,171,27,72,18,693,18,72,27,171,9,702,9,81,18,81,9]
// version 2.0 without using `RegExp`
function getNextLexicographicPermutation(arr) {
var len = arr.length;
var idx = arr.map(function(_, index) {
return index
});
var n = Math.pow(10, len - 1);
var p = 9;
var last = Number(idx.slice().reverse().join(""));
var res = [];
var curr = Number(idx.join(""));
var prev, k, next;
while (curr <= last) {
prev = curr;
k = String(prev).split("").map(Number);
if (k.every(function(v) {
return idx.indexOf(v) !== -1
}) && k.length >= len - 1) {
next = [];
for (var i = 0; i < k.length; i++) {
if (next.indexOf(Number(k[i])) == -1
&& idx.indexOf(Number(k[i])) !== -1) {
next.push(Number(k[i]))
}
}
if (prev < n && next.length === len - 1
|| prev > n && next.length === len)) {
res[res.length] = next.length < len
? [0].concat.apply([0], next)
: next;
}
}
prev += p;
curr = prev;
};
return res.map(function(item) {
return item.map(function(v) {
return arr[v]
})
})
}
getNextLexicographicPermutation(arr)
第二个版本通过将位掩码替换为
RegExp（由 @lleaff 在 最有效的方法检查范围内的数字，而不重复 中回答），大大提高了效率。由于忽略了对所执行的确切测试进行评论，因此使用 DevTools 生成的相关配置文件，无法精确重现以前问题中发布的数字和时间，除非花更多时间验证已发布的数字。当输入集的 .length 为十时，浏览器选项卡可能已崩溃。重要的是，位掩码测试版本比 RegExp 测试版本更高效。// version 2.1, substituting bitmask for `RegExp`
function getNextLexicographicPermutation(arr) {
function checkDigits(min, max, n) {
var digits = 0;
while (n) {
d = (n % 10);
n = n / 10 >> 0;
if (d < min || d > max || (digits & (1 << d)))
return false;
else
digits |= 1 << d;
}
return true;
}
var len = arr.length,
idx = arr.map(function(_, index) {
return index
}),
p = 9,
min = 0,
max = len - 1,
last = Number(idx.slice().reverse().join("")),
res = [],
curr = Number(idx.join("")),
next;
while (curr < last) {
next = (curr += p);
if (checkDigits(min, max, next)) res[res.length] = next;
curr = next;
};
return res.map(function(item) {
var item = String(item).split("").map(Number);
item = item.length < arr.length ? [0].concat(item) : item;
return item.map(function(index) {
return arr[index]
}).filter(Boolean)
})
}
getNextLexicographicPermutation(arr);
这些笔记和过程花费了大部分时间，一年多以前才展示和证明。主要是思考如何同时为斜率两侧获取指数，只使用倾斜度指数，而不编码算法。
大部分的数学工作在于尝试推导相邻九的倍数之间的进一步相关性，以便计算下一个九的倍数的确切值。
9
对于将数字增加九并从结果中过滤重复值的操作。我还没有能够解密相邻的九的倍数之间的相互关系，以至于乘法或除法可以替代加法和排除。
决定最终创建概念证明，证明从无限输入集合中仅使用倾斜度或仅使用可能排列的前半部分加一的索引作为数字，可以生成无限数量的排列。
// version 3, generate second half of permutations using indexes of first
// half of permutations
function getNextLexicographicPermutation(arr) {
for (var l = 1, i = k = arr.length; l < i ; k *= l++);
function checkDigits(min, max, n) {
var digits = 0;
while (n) {
d = (n % 10);
n = n / 10 >> 0;
if (d < min || d > max || (digits & (1 << d)))
return false;
else
digits |= 1 << d;
}
return true;
}
var len = arr.length
, idx = arr.map(function(_, index) {
return index
})
, p = 9
, min = 0
, max = len - 1
, last = Number(idx.slice().reverse().join(""))
, curr = Number(idx.join(""))
, res = []
, diff = []
, result = []
, next;
while (res.length < (k / 2) + 1) {
next = (curr += p);
if (checkDigits(min, max, next)) res[res.length] = next;
curr = next;
};
for (var i = 0; i < res.length; i++) {
var item = res[i];
item = String(item).split("").map(Number);
item = (item.length < arr.length ? [0].concat(item) : item)
.map(function(index) {
return arr[index]
}).filter(Boolean);
result.push(item)
}
res.reduce(function(a, b) {
diff.push(b - a);
return b
});
for (var i = 0, curr = res[res.length - 1], n = diff.length - 2
; result.length < k; i++, n--) {
curr = curr + diff[n];
result.push(
String(curr).split("")
.map(function(index) {
return arr[index]
})
);
}
return result;
}
getNextLexicographicPermutation(arr);
算法开发的另一个潜在步骤是给定任意.length输入，能够通过仅使用单个乘法、除法、代数、三角函数或微积分公式，在数学上计算索引和集合的第n个排列的值。
请在答案中包含可重复的基准测试。原因是不能确切地记住如何在DevTools的Profiles中推导出数字，但如果记得正确，那么在使用时会在相应部分的开头和结尾使用console.time()、console.timeEnd()和console.profile()。备份您的实验；您永远不知道硬盘或操作系统何时会崩溃。通常可以从磁盘中检索数据，但这需要时间和精力。以与保存算法版本相同的方式保存测试结果，以便能够自我复制和供他人复制。原始测试的全部范围已经丢失。
在浏览器标签崩溃之前可以派生多少排列的测试残留只有从不同操作系统检索到的注释。
// 362880 876543210 876543219
var arr = ["a", "b", "c", "d", "e", "f", "g", "h", "i"];
如果我回忆得正确，当将"j"添加到数组时，Chromium浏览器中的活动选项卡会崩溃。第一个数字是从集合“a”到“i”的排列总数；接下来的两个数字可能是，在版本3之前的某个版本上进行的两个测试的结果，尽管不确定，这是今天所构成的。
这是现在在stackoverflow.com发布上述披露的另一个原因，以保留算法的原则和已完成的代码工作，减少一些灾难性的破坏所有原始笔记和工作的风险。例如，连续几天清醒地尝试解释数字之间的模式和关系，忽略在代码注释中记录所有特定测试模式，尝试将算法移植到代码；或者正如@JaromandaX所描述的情况"PEBCAK"。
新的观点可能能够从效率的不同角度看待该算法。
我们可以通过一些保存的代码版本重现一些结果的图表，例如使用console.time()、console.timeEnd()、performance.now()或其他适当的涉及完成该功能所需时间的测试，这些都可以重现。
// console.time("version N");
// getNextLexicographicPermutation(arr);
// console.timeEnd("version N");
var tests = [];
for (var i = 0; i < 10000; i++) {
var from = window.performance.now();
getNextLexicographicPermutation(arr);
tests.push(window.performance.now() - from);
}
for (var i = 0, k = 0; i < tests.length; i++) {
k += tests[i];
}
var avg = k/tests.length;
// version 1 `avg`: 0.2989265000001993
// version 2.0 `avg`: 0.8271295000007376
// version 2.1 `avg`: 0.17173000000003666
// version 3 `avg`: 0.12989749999987543
作为一个脚注，我想提一下，我使用了该算法的原则来推导出在Fastest way to generate all binary strings of size n into a boolean array?中预期的结果，其中数字九再次出现作为倾斜坡度中的关键数字，并且相应的偏角也是可观测的。虽然没有对该问题描述的具体输入和结果形式进行进一步的测试和自动化。该答案证明了忽略值并仅使用类似波浪线的增量模式应用于单个数字初始数字零，以推导出集合的无限排列的方法是可行的。
问题：
How can the algorithm be improved as to efficiency; both computationally and mathematically?
Can we create the indexes for both inclination and declination slope at the same time; rather than determining the declination slope after the inclination slope has been calculated?
Are there a mathematical relationships or patterns between the indexes as numbers, that is, for example, the set of numbers at graph 1, graph 2 or graph 3, derived from the input of any four values, for example
abcd
or
["a", "b", "c", "d"]that the author has not yet to recognize; which could be used to further reduce the number of computations currently implemented to derive results?
javascript的进展和发现。手写笔记和数学计算太多而且各不相同，现在尝试编译还为时过早。这个问题本身花费了大约七个小时来撰写。 - guest2713149,81,18,81,9,702,9,171,27,72,18,693,18,72,27,171,9,702,9,81,18,81,9可以放入整数序列在线百科全书（OEIS®）的搜索中。然后，这将提供到其他参考资料、其他相关序列、序列的见解甚至一些用于生成序列的源代码的链接。 - Guy Coder