没有递归函数调用的排列 [英] Permutations without recursive function call
问题描述
要求：生成集合的所有可能组合的算法，无需重复，或递归调用函数以返回结果。
大多数（如果不是全部）答案在 JavaScript中的排列？中提供，从循环或其他函数中递归调用函数以返回结果。
循环内的递归函数调用示例
函数p（a ，b，res）{
var b = b || []，res = res || []，len = a.length;
if（！len）
res.push（b）
else
for（var i = 0; i< len
//递归调用`p `这里
; p（a.slice（0，i）.concat（a.slice（i + 1，len）），b.concat（a [i]），res）
，i ++
）;
返回res
}
p（[a，b，c]）;
当前的问题试图在线性过程中创建给定的排列，依赖于先前的排列。 / p>
例如，给定一个数组
var arr = [a ，b，c];
确定可能的排列总数
for（var len = 1，i = k = arr.length; len< i; k * = len ++）;
k 应该返回 6 ，或 arr [a，b，c]的可能排列总数
使用为集合确定的单个排列总数，可以使用<创建和填充包含所有六个排列的结果数组code> Array.prototype.slice（）， Array.prototype.concat（）和 Array.prototype .reverse（）
var res = new Array（new Array（k））;
res [0] = arr;
res [1] = res [0] .slice（0,1）.concat（res [0] .slice（-2）.reverse（））;
res [2] = res [1] .slice（-1）.concat（res [1] .slice（0,2））;
res [3] = res [2] .slice（0,1）.concat（res [2] .slice（-2）.reverse（））;
res [4] = res [3] .slice（-2）.concat（res [3] .slice（0,1））;
res [5] = res [4] .slice（0,1）.concat（res [4] .slice（-2）.reverse（））;
尝试根据有序词典排列算法图中显示的模式重现结果基于计算排列和求职面试问题
如果输入集是，例如
[a，b，c，d，e] 其中120个排列将是预期的。
尝试仅依靠先前的排列来填充数组
//在`j`
var arr = [a，b，c，d，e]返回重复的条目，j = [ ]。
var i = k = arr.length;
arr.forEach（function（a，b，array）{
if（b> 1）{
k * = b;
if（b === i -1） ）{
for（var q = 0; j.length< k; q ++）{
if（q === 0）{
j [q] = array;
} else {
j [q] =！（q％i）
？array.slice（q％i）.reverse（）。concat（array.slice（0，q％i））
：array.slice（q％i）.concat（array.slice（0，q％i））;
}
}
}
}
}）
但是还无法对 .concat（）， .reverse（） at above js 从一个排列步进到下一个排列;而只使用 res 中的前一个数组条目来确定当前的排列，而不使用递归。
注意甚至，奇数调用余额并尝试使用模数％运算符和输入数组 .length 来调用 .reverse（）或不在 [a，b，c，d，e] 数组，虽然没有重复条目但没有产生结果。
预期的结果是上述模式可以减少到在过程持续时间内连续调用的两行，直到所有排列已完成， res 已填写;一个用于呼叫 .reverse（），不用 .reverse（）;例如，在 res [0] 填充后
//奇数，如何为未知的`n``。length`数组调整`.slice（）`，`.concat（）`参数
//？
res [i] = res [i - 1] .slice（0,1）.concat（res [i - 1] .slice（-2）.reverse（））;
//偶数
res [i] = res [1 - 1] .slice（-1）.concat（res [i - 1] .slice（0,2））;
问题：需要对上述模式进行哪些调整，特别是传递的参数或索引 .slice（）， .concat（）生成给定集的所有可能排列，而不使用对当前处理的递归调用函数？
var arr = [a， b，c]; for（var len = 1，i = k = arr.length; len< i; k * = len ++）; var res = new Array（new Array（k））; res [ 0] = arr; res [1] = res [0] .slice（0,1）.concat（res [0] .slice（-2）.reverse（））; res [2] = res [1]。 slice（-1）.concat（res [1] .slice（0,2））; res [3] = res [2] .slice（0,1）.concat（res [2] .slice（-2） .reverse（））; res [4] = res [3] .slice（-2）.concat（res [3] .slice（0,1））; res [5] = res [4] .slice（0 ，1）.concat（res [4] .slice（-2）.reverse（））; console.log（res）;
编辑，更新
有发现了一个利用上述模式的流程，以字典顺序返回输入，输入高达 .length 4，使用单个表示循环。对于 .length 5 的数组，不会返回预期结果。
该模式基于计算排列和工作面试问题的第二个图表 [ 0 ] 。
不愿意不使用 .splice（）或 .sort（）返回结果，尽管在此处使用时尝试遵守最后每列旋转要求。变量 r 应该引用下一个排列的第一个元素的索引。
使用 .splice（）， .sort（）;虽然在 js 下面，但它们实际上没有。
不完全确定之后的声明if（i％（total / len）=== reset），尽管该部分需要投入最多时间但是仍然没有返回预期的结果。
具体来说，现在参考图表，在旋转时，例如 2 索引 0 ， 1 索引 2 。试图通过使用 r （这是一个负面索引）从右到左遍历以检索应位于 index <的下一个项目来实现此目的/ code> 0 相邻的列。
在下一栏， 2 将被放置在索引 2 ， 3 将被放置在 index 0 。到目前为止，这是能够掌握或调试的部分，是发生错误的区域。
同样，返回 [1,2,3,4] 的预期结果，但不是 [1,2,3,4,5]
var arr = [1,2,3,4]; for（var l = 1，j = total = arr.length; l< j; total * = l ++）; for（var i = 1，reset = 0，idx = 0，r = 0，len = arr.length，res = [arr]; i< total; i ++）{// previous permutation var prev = res [i-1]; //如果我们在这里排列6，或者完成以1开头的所有//排列; //设置下一个列，将`2`放在`index` 0; //遵循以`2`开头的所有排列，将`3`放在//`index``0`;如果（i％（总/ len）===重置）{r = - r％ - （len）;对于`3`到'4`的过程相同var next = prev.slice（r）; if（r === -1）{//用于将索引`-1` //的项设置为`索引`0的第一个实现//更倾向于对所有旋转使用单个进程，//而不是拆分进入`if`，`else`，虽然不存在，但res [i] = [next [0]]。concat（prev.slice（0,1），prev.slice（1，len - 1）.reverse（ ））; } else {//从`index``r`到`index``0`的旋转的解决方法//图表实际上并没有在这里使用先前的排列，//而是，该特定的第一个排列柱; //这里，使用`r``，i`，`len`，将是//`res [i - （i - 1）％（total / len）]`var curr = prev.slice（）; //这可能很有用，在`r``index`curr.splice（prev.indexOf（next [0]），1）中检索`r`，//`prev`没有项目; //这不是optiomal curr.sort（function（a，b）{return arr.indexOf（a）> arr.indexOf（b）}）; //将`next` [0]`放在`index``0` //将排序数组的剩余部分放在`index``1` - n curr.splice（0,0，next [0]）res [i] = curr} idx = reset; } else {if（i％2）{// odd res [i] = prev.slice（0，len - 2）.concat（prev.slice（-2）.reverse（））} else {// even - -idx res [i] = prev.slice（0，len - （len - 1））。concat（prev.slice（idx），prev.slice（1，len +（idx）））}}} // try使用`arr`：`[1,2,3,4,5]`来返回不正确的`res`; //如何调整`js`以返回`[1,2,3]的正确结果，4,5]`？console.log（res，res.length）
资源：
（倒计时）QuickPerm头词典：
（正式例子_03~回文）
全部生成排列[非递归]
（尝试从 C ++ 移植到 javascript jsfiddle http://jsfiddle.net/tvvvjf3p/ ）
是否可以在O（n log n）时间内生成集合或字符串的所有排列？
这是计算字符串第n个排列的简单解决方案：
function string_nth_permutation（str，n）{
var len = str.length，i，f，res;
for（f = i = 1; i< = len; i ++）
f * = i;
if（n> = 0&& n< f）{
for（res =; len> 0; len--）{
f / = len;
i = Math.floor（n / f）;
n％= f;
res + = str.charAt（i）;
str = str.substring（0，i）+ str.substring（i + 1）;
}
}
返回res;
}
该算法遵循以下简单步骤：
- 首先计算
f = len！，有factorial（len）一组len不同元素的总排列。 - 作为第一个元素，将排列数除以
（len-1）！并在结果偏移处选择元素。有（len-1）！具有任何给定元素作为其第一个元素的不同排列。 - 从中删除所选元素设置并使用除法的其余部分作为排列编号继续前进。
- 对集合的其余部分执行这些步骤，其长度减少一个。
此算法非常简单且具有有趣的属性：
- 它直接计算第n个排列。
- 如果订单是有序的，排列是按字典顺序生成的。
- 即使设置了元素也能正常工作无法相互比较，例如对象，数组，函数...
- 排列数
0是订单中的集合给定。 - 置换数
factorial（a.length）-1是最后一个：集合a以相反的顺序。 - 此范围之外的排列将以未定义的形式返回。
它可以很容易地转换为处理存储为数组的集合：
function array_nth_permutation（a，n）{
var b = a.slice（）; //集合的副本
var len = a.length; //集合
var res的长度; //返回值，undefined
var i，f;
//计算f = factorial（len）
for（f = i = 1; i< = len; i ++）
f * = i;
//如果排列数在
范围内，如果（n> = 0&& n< f）{
//以空集开头， len元素的循环
for（res = []; len> 0; len--）{
//确定下一个元素：
//每个都有f / len子集可能的元素，
f / = len;
//一个简单的除法给出了前导元素索引
i = Math.floor（n / f）;
//交替地：i =（n - n％f）/ f;
res.push（b.splice（i，1）[0]）;
//为剩余子集减少n：
//计算上述除法的剩余部分
n％= f;
//从b中提取第i个元素并在res
结束时将其推送到
}
//返回置换集合或如果n超出范围则未定义
返回res;
}
澄清：
-
f首先计算为factorial（len）。 - 对于每一步，
f除以len，给出前一个阶乘。 -
n除以此新值f给出<$中的插槽号c $ c> len 具有相同初始元素的插槽。 Javascript没有整数除法，我们可以使用（n / f）... 0）将除法的结果转换为其整数部分，但它引入了一个限制一套12个元素。Math.floor（n / f）允许最多18个元素的集合。我们也可以使用（n - n％f）/ f，也可能更高效。 -
n必须减少到此插槽中的排列编号，即除法的剩余部分n / f。
我们可以在第二个循环中使用 i ，存储除法余数，避免 Math.floor（）和额外的％运算符。以下是此循环的替代方法，可能甚至不太可读：
//从空集，len元素循环
for（res = []; len> 0; len--）{
i = n％（f / = len）;
res.push（b.splice（（n - i）/ f，1）[0]）;
n = i;
}
Requirement: Algorithm to generate all possible combinations of a set , without duplicates , or recursively calling function to return results.
The majority , if not all of the Answers provided at Permutations in JavaScript? recursively call a function from within a loop or other function to return results.
Example of recursive function call within loop
function p(a, b, res) {
var b = b || [], res = res || [], len = a.length;
if (!len)
res.push(b)
else
for (var i = 0; i < len
// recursive call to `p` here
; p(a.slice(0, i).concat(a.slice(i + 1, len)), b.concat(a[i]), res)
, i++
);
return res
}
p(["a", "b", "c"]);
The current Question attempts to create the given permutation in a linear process , relying on the previous permutation.
For example , given an array
var arr = ["a", "b", "c"];
to determine the total number of possible permutations
for (var len = 1, i = k = arr.length; len < i ; k *= len++);
k should return 6 , or total number of possible permutations of arr ["a", "b", "c"]
With the total number of individual permutations determined for a set , the resulting array which would contain all six permutations could be created and filled using Array.prototype.slice() , Array.prototype.concat() and Array.prototype.reverse()
var res = new Array(new Array(k));
res[0] = arr;
res[1] = res[0].slice(0,1).concat(res[0].slice(-2).reverse());
res[2] = res[1].slice(-1).concat(res[1].slice(0,2));
res[3] = res[2].slice(0,1).concat(res[2].slice(-2).reverse());
res[4] = res[3].slice(-2).concat(res[3].slice(0,1));
res[5] = res[4].slice(0,1).concat(res[4].slice(-2).reverse());
Attempted to reproduce results based on the pattern displayed at the graph for An Ordered Lexicographic Permutation Algorithm based on one published in Practical Algorithms in C++ at Calculating Permutations and Job Interview Questions .
There appears to be a pattern that could be extended if the input set was , for example
["a", "b", "c", "d", "e"]
where 120 permutations would be expected.
An example of an attempt at filling array relying only on previous permutation
// returns duplicate entries at `j`
var arr = ["a", "b", "c", "d", "e"], j = [];
var i = k = arr.length;
arr.forEach(function(a, b, array) {
if (b > 1) {
k *= b;
if (b === i -1) {
for (var q = 0;j.length < k;q++) {
if (q === 0) {
j[q] = array;
} else {
j[q] = !(q % i)
? array.slice(q % i).reverse().concat(array.slice(0, q % i))
: array.slice(q % i).concat(array.slice(0, q % i));
}
}
}
}
})
however have not yet been able to make the necessary adjustments at parameters for .slice() , .concat() , .reverse() at above js to step from one permutation to the next ; while only using the previous array entry within res to determine current permutation , without using recursive.
Noticed even , odd balance of calls and tried to use modulus % operator and input array .length to either call .reverse() or not at ["a", "b", "c", "d", "e"] array , though did not produce results without duplicate entries.
The expected result is that the above pattern could be reduced to two lines called in succession for the duration of the process until all permutations completed, res filled ; one each for call to .reverse() , call without .reverse() ; e.g., after res[0] filled
// odd , how to adjust `.slice()` , `.concat()` parameters
// for array of unknown `n` `.length` ?
res[i] = res[i - 1].slice(0,1).concat(res[i - 1].slice(-2).reverse());
// even
res[i] = res[1 - 1].slice(-1).concat(res[i - 1].slice(0,2));
Question: What adjustments to above pattern are necessary , in particular parameters , or index , passed .slice() , .concat() to produce all possible permutations of a given set without using a recursive call to the currently processing function ?
var arr = ["a", "b", "c"];
for (var len = 1, i = k = arr.length; len < i; k *= len++);
var res = new Array(new Array(k));
res[0] = arr;
res[1] = res[0].slice(0, 1).concat(res[0].slice(-2).reverse());
res[2] = res[1].slice(-1).concat(res[1].slice(0, 2));
res[3] = res[2].slice(0, 1).concat(res[2].slice(-2).reverse());
res[4] = res[3].slice(-2).concat(res[3].slice(0, 1));
res[5] = res[4].slice(0, 1).concat(res[4].slice(-2).reverse());
console.log(res);
Edit, Update
Have found a process to utilize pattern described above to return permutations in lexicographic order for an input up to .length 4 , using a single for loop. Expected results are not returned for array with .length of 5.
The pattern is based on the second chart at "Calculating Permutations and Job Interview Questions"[0].
Would prefer not to use .splice() or .sort() to return results, though used here while attempting to adhere to last "rotate" requirement at each column. The variable r should reference the index of the first element of the next permutation, which it does.
The use of .splice() , .sort() could be included if their usage followed the pattern at the chart ; though at js below, they actually do not.
Not entirely certain that the issue with js below is only the statement following if (i % (total / len) === reset) , though that portion required the most investment of time; yet still does not return expected results.
Specifically, now referring to the chart, at rotating , for example 2 to index 0, 1 to index 2. Attempted to achieve this by using r , which is a negative index, to traverses from right to left to retrieve next item that should be positioned at index 0 of adjacent "column".
At next column, 2 would be placed at index 2 , 3 would be placed at index 0. This is portion, as far as have been able to grasp or debug, so far, is the area where error is occurring.
Again, returns expected results for [1,2,3,4], though not for [1,2,3,4,5]
var arr = [1, 2, 3, 4];
for (var l = 1, j = total = arr.length; l < j ; total *= l++);
for (var i = 1
, reset = 0
, idx = 0
, r = 0
, len = arr.length
, res = [arr]
; i < total; i++) {
// previous permutation
var prev = res[i - 1];
// if we are at permutation `6` here, or, completion of all
// permutations beginning with `1`;
// setting next "column", place `2` at `index` 0;
// following all permutations beginning with `2`, place `3` at
// `index` `0`; with same process for `3` to `4`
if (i % (total / len) === reset) {
r = --r % -(len);
var next = prev.slice(r);
if (r === -1) {
// first implementation used for setting item at index `-1`
// to `index` 0
// would prefer to use single process for all "rotations",
// instead of splitting into `if` , `else`, though not there, yet
res[i] = [next[0]].concat(prev.slice(0, 1), prev.slice(1, len - 1)
.reverse());
} else {
// workaround for "rotation" at from `index` `r` to `index` `0`
// the chart does not actually use the previous permutation here,
// but rather, the first permutation of that particular "column";
// here, using `r` `,i`, `len`, would be
// `res[i - (i - 1) % (total / len)]`
var curr = prev.slice();
// this may be useful, to retrieve `r`,
// `prev` without item at `r` `index`
curr.splice(prev.indexOf(next[0]), 1);
// this is not optiomal
curr.sort(function(a, b) {
return arr.indexOf(a) > arr.indexOf(b)
});
// place `next[0]` at `index` `0`
// place remainder of sorted array at `index` `1` - n
curr.splice(0, 0, next[0])
res[i] = curr
}
idx = reset;
} else {
if (i % 2) {
// odd
res[i] = prev.slice(0, len - 2).concat(prev.slice(-2)
.reverse())
} else {
// even
--idx
res[i] = prev.slice(0, len - (len - 1))
.concat(prev.slice(idx), prev.slice(1, len + (idx)))
}
}
}
// try with `arr` : `[1,2,3,4,5]` to return `res` that is not correct;
// how can above `js` be adjusted to return correct results for `[1,2,3,4,5]` ?
console.log(res, res.length)
Resources:
Generating Permutation with Javascript
(Countdown) QuickPerm Head Lexicography: (Formally Example_03 ~ Palindromes)
Generating all Permutations [non-recursive]
(Attempt to port to from C++ to javascript jsfiddle http://jsfiddle.net/tvvvjf3p/)
Calculating Permutation without Recursion - Part 2
permutations of a string using iteration
Evaluation of permutation algorithms
Permutation algorithm without recursion? Java
Non-recursive algorithm for full permutation with repetitive elements?
String permutations in Java (non-recursive)
Generating permutations lazily
How to generate all permutations of a list in Python
Can all permutations of a set or string be generated in O(n log n) time?
Finding the nth lexicographic permutation of ‘0123456789’
Here is a simple solution to compute the nth permutation of a string:
function string_nth_permutation(str, n) {
var len = str.length, i, f, res;
for (f = i = 1; i <= len; i++)
f *= i;
if (n >= 0 && n < f) {
for (res = ""; len > 0; len--) {
f /= len;
i = Math.floor(n / f);
n %= f;
res += str.charAt(i);
str = str.substring(0, i) + str.substring(i + 1);
}
}
return res;
}
The algorithm follows these simple steps:
- first compute
f = len!, there arefactorial(len)total permutations of a set oflendifferent elements. - as the first element, divide the permutation number by
(len-1)!and chose the element at the resulting offset. There are(len-1)!different permutations that have any given element as their first element. - remove the chosen element from the set and use the remainder of the division as the permutation number to keep going.
- perform these steps with the rest of the set, whose length is reduced by one.
This algorithm is very simple and has interesting properties:
- It computes the n-th permutation directly.
- If the set is ordered, the permutations are generated in lexicographical order.
- It works even if set elements cannot be compared to one another, such as objects, arrays, functions...
- Permutation number
0is the set in the order given. - Permutation number
factorial(a.length)-1is the last one: the setain reverse order. - Permutations outside this range are returned as undefined.
It can easily be converted to handle a set stored as an array:
function array_nth_permutation(a, n) {
var b = a.slice(); // copy of the set
var len = a.length; // length of the set
var res; // return value, undefined
var i, f;
// compute f = factorial(len)
for (f = i = 1; i <= len; i++)
f *= i;
// if the permutation number is within range
if (n >= 0 && n < f) {
// start with the empty set, loop for len elements
for (res = []; len > 0; len--) {
// determine the next element:
// there are f/len subsets for each possible element,
f /= len;
// a simple division gives the leading element index
i = Math.floor(n / f);
// alternately: i = (n - n % f) / f;
res.push(b.splice(i, 1)[0]);
// reduce n for the remaining subset:
// compute the remainder of the above division
n %= f;
// extract the i-th element from b and push it at the end of res
}
}
// return the permutated set or undefined if n is out of range
return res;
}
clarification:
fis first computed asfactorial(len).- For each step,
fis divided bylen, giving exacty the previous factorial. ndivided by this new value offgives the slot number among thelenslots that have the same initial element. Javascript does not have integral division, we could use(n / f) ... 0)to convert the result of the division to its integral part but it introduces a limitation to sets of 12 elements.Math.floor(n / f)allows for sets of up to 18 elements. We could also use(n - n % f) / f, probably more efficient too.nmust be reduced to the permutation number within this slot, that is the remainder of the divisionn / f.
We could use i differently in the second loop, storing the division remainder, avoiding Math.floor() and the extra % operator. Here is an alternative for this loop that may be even less readable:
// start with the empty set, loop for len elements
for (res = []; len > 0; len--) {
i = n % (f /= len);
res.push(b.splice((n - i) / f, 1)[0]);
n = i;
}
这篇关于没有递归函数调用的排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
