这里必须注意，我是在纸上手工进行数学运算的，以得出前述证明。我不确定仅通过使用现代计算机的媒介就可以证明这些证据。
下文所用的“效率”的定义意味着在最短的时间内完成算法的离散部分或整个算法。无论是在数学上，在编程上还是在计算上。
在进一步检查用于从原始集合或当前排列生成下一个字典顺序的过程的过程中，在重新读取Permutations without recursive function call上的@chqrlie的Answer之后，我通过在纸上写下索引来尝试查询索引，以观察两者之间的任何数学关系。可以用来执行特定任务的索引。
我发现了几个有趣的事实，其证明如下所示。
例如，当我们编写值时
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处的值。当我们尝试绘制
12和21之间的潜在关系时，我们发现21 - 12 = 9
当我们继续时，我们发现下一个词典索引是
102
减去先前的索引
102 - 21 = 81
其中
102是下一个字典编排，表示为值bac
这为我们提供了索引之间的通用关系，即数字九表示为九
9
对于表示为数字的无限一组输入值，这种关系是显而易见的并可重现的。我们可以绘制关系图，视观察者的 Angular 而定，可以将它们视为两个斜率，当从结果排列的集合的第一个值开始绘制图时，顶点的偏移为倒数
// 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的加法或乘法来计算，生成，过滤，导出给定无穷输入集的无穷排列集的证明。
9
通过匹配仅包含输入数字的索引号的数字，而集合中没有重复的数字。
此外，我证明了仅需要索引作为倾斜度上的数字或可能的排列总数除以2加1即可得出给定输入的排列总数。
正如这篇文章的前言所强调的那样，如果不花大量时间在纸上进行手工数学运算，那么可能无法进行这种计算。简单的媒体屏幕不能提供与在纸上一个接一个地构成字符相同的媒体；能够从各种物理尺寸查看纸张。
使用编码语言表达算法本身是另一项任务。
以下是使用“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)
通过使用Most efficient method to check for range of numbers within number without duplicates处的@lleaff的答案将位掩码替换为
RegExp，大大提高了第二个版本的效率。在chromet浏览器中，由
DevTools版本和bitmask版本之间的RegExp生成的相关配置文件应该是可复制的，但是由于忽略了对执行的确切测试的注释，因此无法准确地重现发布的数字和时间，而没有花费更多时间来验证发布的数字在上一个问题。记不清了，尽管输入集的.length为10时浏览器选项卡可能崩溃。重要的是，位掩码测试版本比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
用于将数字增加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个排列的值；通过仅使用一个乘法，除法，代数，三角法或微积分的公式。请在Answer中包含可复制的基准。原因是，虽然记住正确使用的
Profiles，DevTools和console.time()在使用的各个部分的开头和结尾，但无法确切记住我如何在console.timeEnd()上获取console.profile()的数字。备份实验；您永远不会知道硬盘或操作系统是否或何时崩溃。通常，您可以从磁盘上检索数据，但是这样做会花费时间和精力。以与保存算法版本相同的方式保存测试，以实现自我复制和他人复制的能力。原始测试的全部色域丢失了。在浏览器选项卡崩溃之前，可以得出多少排列的测试的剩余内容仅是从其他操作系统检索到的注释
// 362880 876543210 876543219
var arr = ["a", "b", "c", "d", "e", "f", "g", "h", "i"];
如果准确地收集信息，则在将
"j"添加到阵列时， Chrome 的 Activity 选项卡崩溃了。第一个数字是集合“a”到“i”的排列总数；接下来的两个数字可能(尽管不确定)是针对今天构成的第3版之前的其中一个版本的两次测试的结果。这就是现在将上述公开内容发布在stackoverflow.com上的另一个原因，以保留该算法的原理和到目前为止已完成的代码上的工作，而少了一些灾难性破坏所有原始注释和工作；例如，连续数天醒着，试图解释数字之间的模式和关系；忽略记录所有特定的测试模式，试图将算法移植到代码中的注释处；或@JaromandaX描述情况"PEBCAK"。
新手可能会从效率的不同 Angular 看待该算法。
我们可以重现上面保留的一些代码版本的结果图，例如，使用
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?上获得了预期的结果，在这里，数字9再次显示为倾斜度内的关键数字，并且倾斜度的匹配 Angular 也是可以观察到的。尽管没有对该问题所描述的输入和结果的特定形式进行进一步的测试和自动化。答案是关于方法的可行性的概念证明，该方法忽略了这些值，而仅对单个数字初始数零使用仅波浪形的递增模式来导出集合的无限置换。
问题:
计算和数学上？
abcd
要么
["a", "b", "c", "d"]
作者尚未认识到；可以用来
进一步减少当前实现的计算数量
得出结果？
最佳答案
TL； DR版本
不幸的是，提高该算法性能的唯一方法是摆脱它，而使用更好的东西。
“真相”明显吗？ (扰流板警报:是的，它们是)
在您的长篇文章中，我看到了您发现的两个“真相”:
不幸的是，这两个事实都很明显，其中之一甚至不是真的。
只要数组的长度小于10，则第一个事实为真。如果大于10，即某些索引被“映射”为2个字符，则它不再为真。而且，如果您知道divisibility rule for 9(以十进制表示)，这显然是正确的:数字的总和应为9的倍数。显然，如果两个数字具有相同的数字，则它们具有相同的提醒模块9，因此它们的差是一个乘法of9。此外，如果您在任何基数大于数组长度的系统中解释字符串，出于相同的原因，差异将是
base - 1的倍数。例如，让我们使用基于8的系统(列为:排列，排列索引，索引字符串，从8转换为十进制的索引字符串，差值):abc 0 012 10
acb 1 021 17 7
bac 2 102 66 49
bca 3 120 80 14
cab 4 201 129 49
cba 5 210 136 7
如果您始终使用大于数组长度的系统，那么这个事实是正确的(但是您可能需要输入新的数字)
第二个陈述也是显而易见的，并且是如何定义“字典顺序”的直接后果。对于每个索引
i，如果我对第一个i-th排列和最后一个i-th排列的索引数组求和，则总和将始终相同:所有值等于数组长度的数组。例:1. abc 012 - cba 210 => 012 + 210 = 222
2. acb 021 - cab 201 => 021 + 201 = 222
3. bac 102 - bca 120 => 102 + 120 = 222
这很容易看出是否考虑了负索引数组
[-N, -(N-1), ..., -1, 0]的排列。显然，从此数组的开头开始的i-th排列与从结尾开始的i-th的[0, 1, 2, ... N]排列(仅带有负号)相同。其他问题
- 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
是的，有。实际上，这正是您在问题Permutations without recursive function call中链接的答案首先起作用的原因。但是我怀疑有没有一种算法比该答案中提供的算法效率更高。有效地，该答案试图将所请求排列的位置转换为以1为基数到数组长度的底数的可变基数值系统中的值。 (对于可变基数值系统的更广泛的示例，请考虑如何将毫秒转换为几天-小时-分钟-秒-毫秒。您可以有效地使用基数为1000-60-60-24-unlimited的数值系统。因此，当您看到
12345 days 8 hours 58 minutes 15 seconds 246 milliseconds将您将其转换为毫秒作为((((12345 * 24 + 8) * 60) + 58 * 60) + 15) * 1000 + 246，即您将该表示法视为12345 (no base/unlimited) days 8 (24-base) hours 58 (60 base) minutes 15 (60 base) seconds 246 (1000-base) milliseconds)。使用置换，您可能需要执行两个不同的任务:
i-th排列。您在SO答案中链接的算法相当有效。我怀疑还有什么更好的更新(评论的答案)
What I claim is that there is no way to calculate the sequence of numbers that would be more efficient than a direct calculation of the sequence of permutations.
我不同意这个主张。您可以证明这一主张吗？
不，我什至不知道如何以正式的方式陈述这一主张(如何定义不计算该数字序列的算法类别？)。我仍然有一些证据支持这一点。
首先，您可能不是已知宇宙中最聪明的人，这是一个相对古老且广为人知的话题。因此，您发现比现有算法快得多的算法的机会很小。而且没有人使用此技巧的事实也证明了您的不对。
还有一点不是那么随意:我在＃2建议的用于顺序生成所有排列的算法实际上是相当有效的，因此很难被击败。
考虑一些步骤来查找下一个排列。首先，您需要从不降序的末尾找到第一个位置。假设它将是k。找到它需要k比较。然后，您需要进行一次交换和排序。但是，如果您比较聪明，您可能会注意到这里的“排序”可能会更快，因为列表已经排序(但是顺序相反)。因此，这里的排序与找到k-th元素的位置恰好相反。并且考虑到数组已排序，您可以使用O(log(k))复杂度的二进制搜索。因此，您需要将k+1元素移动到内存中，并且比k的比较少。这是一些代码:// generates array of all permutatations of array of integers [0, 1, .., n-1] function permutations(n) { // custom version that relies on a fact that all values are unique i.e. there will be no equality var binarySearch = function (tgt, arr, start, end) { // on small ranges direct loop might be more efficient than actual binary search var SMALL_THRESHOLD = 5; if (start - end < SMALL_THRESHOLD) { for (var i = start; i <= end; i++) { if (arr[i] > tgt) return i; } throw new Error("Impossible"); } else { var left = start; var right = end; while (left < right) { var middle = (left + right) >> 1; //safe /2 var middleV = arr[middle]; if (middleV < tgt) { left = middle + 1; } else { right = middle; } } return left; } }; var state = []; var allPerms = []; var i, swapPos, swapTgtPos, half, tmp; for (i = 0; i < n; i++) state [i] = i //console.log(JSON.stringify(state)); allPerms.push(state.slice()); // enfroce copy if (n > 1) { while (true) { for (swapPos = n - 2; swapPos >= 0; swapPos--) { if (state[swapPos] < state[swapPos + 1]) break; } if (swapPos < 0) // we reached the end break; // reverse end of the array half = (n - swapPos) >> 1; // safe /2 for (i = 1; i < half + 1; i++) { //swap [swapPos + i] <-> [n - i] tmp = state[n - i]; state[n - i] = state[swapPos + i]; state[swapPos + i] = tmp; } // do the final swap swapTgtPos = binarySearch(state[swapPos], state, swapPos + 1, n - 1); tmp = state[swapTgtPos]; state[swapTgtPos] = state[swapPos]; state[swapPos] = tmp; //console.log(JSON.stringify(state)); allPerms.push(state.slice()); // enfroce copy } } //console.log("n = " + n + " count = " + allPerms.length); return allPerms; }
现在，假设您对基于数字的方法进行了相同的处理，并且暂时假设您可以立即计算要为每个步骤添加的数字。那么，您现在使用多少时间？由于您必须使用长算术，并且我们知道，加法将更改的最高位数为k-th，因此您至少需要执行k加法和k比较以防止溢出。当然，您仍然至少必须将k写入内存。因此，要比上述“常规”算法更有效，您需要一种方法来计算k-位数长数字(您将添加的数字)，而所需时间要比对k大小的数组执行二进制搜索要少。在我看来，这是一项艰巨的工作。例如，使用长算法将9(或更确切地说是N-1)乘以相应的系数可能会花费更多的时间。
那么，您还有其他机会吗？根本不要使用长运算。在这种情况下，第一个显而易见的论据是，在数学上比较小N上的算法性能几乎没有意义(这就是为什么Big-O notation用于算法复杂性的原因)。从纯数学的 Angular 来看，为“小”的性能而奋斗还是有道理的，但对于现实情况中的“大”，直到20个元素的排列排列仍然可以适应较长(64-位)的整数。那么，不使用长运算就可以获得什么呢？好吧，您的加法和乘法将仅需要一条CPU指令。但是随后您将不得不使用除法将您的数字除以数字，并且每一步都需要N除法和N检查(即比较)。而且N总是大于k，通常更大。因此，这似乎也不是提高性能的绝佳途径。
综上所述:建议的算法是有效的，任何基于算术的算法在算术部分都可能效率较低。
关于javascript - 如何提高生成下一个字典顺序的算法的效率？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/43290467/