没有递归函数调用的排列-Java 学习之路

要求：生成集合的所有可能组合的算法，无需重复，或递归调用函数以返回结果 .

在Permutations in JavaScript?提供的大多数（如果不是全部）Answers以递归方式从循环或其他函数中调用函数来返回结果 .

循环内的递归函数调用示例

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"]);

当前的问题试图在线性过程中创建给定的排列，依赖于先前的排列 .

例如，给定一个数组

var arr = ["a", "b", "c"];

确定可能的排列总数

for (var len = 1, i = k = arr.length; len < i ; k *= len++);

k 应返回 6 ，或 arr ["a", "b", "c"] 的可能排列总数

使用为集合确定的单个排列的总数，可以使用 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());

尝试基于在有序词典排列算法的图表上显示的模式重现结果，该算法基于在Calculating Permutations and Job Interview Questions的C中的实用算法中公布的模式 .

例如，如果输入集是似乎可以扩展的模式

["a", "b", "c", "d", "e"]

预计会有120种排列 .

尝试仅依靠先前的排列来填充数组的示例

// 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));
      }
    }
  }
 }
})

但是，尚未能够在 .slice() ， .concat() ， .reverse() 的参数上进行必要的调整，以便从一个排列步进到下一个排列;而只使用 res 中的前一个数组条目来确定当前的排列，而不使用递归 .

注意甚至，奇怪的调用 balancer 并试图使用模数 % 运算符和输入数组 .length 来调用 .reverse() 或不在 ["a", "b", "c", "d", "e"] 数组，但没有产生没有重复条目的结果 .

预期的结果是上述模式可以减少到在过程持续时间内连续调用的两行，直到所有排列完成， res 填充;每个呼叫 .reverse() 一个，呼叫没有 .reverse() ;例如，在 res[0] 填写之后

// 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));

问题：对上面的模式进行哪些调整是必要的，特别是参数或索引，传递 .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 循环以字典顺序返回输入到 .length 4的输入 . 5 的 .length 数组不会返回预期结果 .

该模式基于"Calculating Permutations and Job Interview Questions" [0]处的第二个图表 .

宁愿不使用 .splice() 或 .sort() 来返回结果，尽管在此处使用时尝试遵守每列的最后"rotate"要求 . 变量 r 应该引用下一个排列的第一个元素 index .

如果它们的使用遵循图表中的模式，则可以包括 .splice() ， .sort() 的使用;虽然在 js 以下，但他们实际上并没有 .

不完全确定下面 js 的问题只是 if (i % (total / len) === reset) 之后的声明，尽管该部分需要最多的时间投入;但仍未返回预期结果 .

具体来说，现在参考图表，在旋转时，例如 2 索引 0 ， 1 索引 2 . 尝试通过使用 r （负索引）来实现此目的，从右到左遍历以检索应位于相邻"column"的 index 0 的下一个项目 .

在下一栏， 2 将被放置在 index 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];
  // 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)

资源：

Generating Permutation with Javascript

(Countdown) QuickPerm Head Lexicography: (Formally Example_03 ~ Palindromes)

Generating all Permutations [non-recursive]（尝试从 C++ 移植到 javascript jsfiddle http://jsfiddle.net/tvvvjf3p/）

Calculating Permutation without Recursion - Part 2

permutations of a string using iteration

iterative-permutation

Permutations by swapping

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’

Combinations and Permutations

8 回答

这可能是另一个解决方案，灵感来自Steinhaus-Johnson-Trotter algorithm：

function p(input) {
  var i, j, k, temp, base, current, outputs = [[input[0]]];
  for (i = 1; i < input.length; i++) {
    current = [];
    for (j = 0; j < outputs.length; j++) {
      base = outputs[j];
      for (k = 0; k <= base.length; k++) {
        temp = base.slice();
        temp.splice(k, 0, input[i]);
        current.push(temp);
      }
    }
    outputs = current;
  }
  return outputs;
}

// call

var outputs = p(["a", "b", "c", "d"]);
for (var i = 0; i < outputs.length; i++) {
  document.write(JSON.stringify(outputs[i]) + "
");
}

回复于 2024-04-19T00:36:22+08:00

这是计算第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);
        }
    }
    return res;
}

该算法遵循以下简单步骤：

首先计算 f = len! ， factorial(len) 有一组 len 个不同元素的总排列 .
作为第一个元素，将置换数除以 (len-1)! 并在结果偏移处选择元素 . 有 (len-1)! 个不同的排列，任何给定的元素作为它们的第一个元素 .
从集合中删除所选元素，并使用除法的余数作为置换数来继续 .
对集合的其余部分执行这些步骤，其长度减少1 .

该算法非常简单，具有有趣的特性：

它直接计算第n个排列 .
如果订购了该集，则按字典顺序生成排列 .
即使set元素无法相互比较，它也可以工作，例如对象，数组，函数......
排列编号 0 是给定顺序的集合 .
排列号 factorial(a.length)-1 是最后一个：以相反的顺序设置 a .
此范围之外的排列将返回为undefined .

它可以很容易地转换为处理存储为数组的集合：

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;
}

澄清：

f 首先计算为 factorial(len) .
对于每一步， f 除以 len ，精确地给出前一个阶乘 .
n 除以 f 的新值，给出具有相同初始元素的 len 槽中的槽号 . Javascript没有整数除法，我们可以使用 (n / f) ... 0) 将除法的结果转换为其整数部分，但它对12个元素的集合引入了限制 . Math.floor(n / f) 允许最多18个元素的集合 . 我们也可以使用 (n - n % f) / f ，也可能更高效 .
n 必须缩减为此插槽中的排列编号，即除法的剩余部分 n / f .

我们可以在第二个循环中使用 i ，存储除法余数，避免 Math.floor() 和额外的 % 运算符 . 以下是此循环的替代方案，可能更不易读取：

// 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;
        }

回复于 2024-04-19T00:36:22+08:00

我认为post应该对你有所帮助 . 该算法应该可以轻松转换为JavaScript（我认为它已经超过70％已经与JavaScript兼容） .

如果您追求效率， slice 和 reverse 是不好的通话 . 帖子中描述的算法遵循next_permutation函数的最有效实现，甚至集成在某些编程语言中（例如C）

EDIT

当我再次迭代算法时，我认为你可以删除变量的类型，你应该很好地使用JavaScript .

EDIT

JavaScript版本：

function nextPermutation(array) {
    // Find non-increasing suffix
    var i = array.length - 1;
    while (i > 0 && array[i - 1] >= array[i])
        i--;
    if (i <= 0)
        return false;

    // Find successor to pivot
    var j = array.length - 1;
    while (array[j] <= array[i - 1])
        j--;
    var temp = array[i - 1];
    array[i - 1] = array[j];
    array[j] = temp;

    // Reverse suffix
    j = array.length - 1;
    while (i < j) {
        temp = array[i];
        array[i] = array[j];
        array[j] = temp;
        i++;
        j--;
    }
    return true;
}

回复于 2024-04-19T00:36:22+08:00

创建排列的一种方法是到目前为止在所有结果中的元素之间的所有空间中添加每个元素 . 这可以在没有使用循环和队列的递归的情况下完成 .

JavaScript代码：

function ps(a){
  var res = [[]];

  for (var i=0; i<a.length; i++){
    while(res[res.length-1].length == i){
      var l = res.pop();
      for (var j=0; j<=l.length; j++){
        var copy = l.slice();
        copy.splice(j,0,a[i]);
        res.unshift(copy);
      }
    }
  }
  return res;
}

console.log(JSON.stringify(ps(['a','b','c','d'])));

回复于 2024-04-19T00:36:22+08:00

这是我自己提出的一种方法的片段，但自然也能找到它described elsewhere：

generatePermutations = function(arr) {
  if (arr.length < 2) {
    return arr.slice();
  }
  var factorial = [1];
  for (var i = 1; i <= arr.length; i++) {
    factorial.push(factorial[factorial.length - 1] * i);
  }

  var allPerms = [];
  for (var permNumber = 0; permNumber < factorial[factorial.length - 1]; permNumber++) {
    var unused = arr.slice();
    var nextPerm = [];
    while (unused.length) {
      var nextIndex = Math.floor((permNumber % factorial[unused.length]) / factorial[unused.length - 1]);
      nextPerm.push(unused[nextIndex]);
      unused.splice(nextIndex, 1);
    }
    allPerms.push(nextPerm);
  }
  return allPerms;
};

Enter comma-separated string (e.g. a,b,c):


<input id="arrInput" type="text" />


<button onclick="perms.innerHTML = generatePermutations(arrInput.value.split(',')).join('
')">
  Generate permutations
</button>


<div id="perms"></div>

Explanation

由于给定数组 arr 有 factorial(arr.length) 个排列， 0 和 factorial(arr.length)-1 之间的每个数字都编码一个特定的排列 . 要取消置换排列编号，请重复删除 arr 中的元素，直到没有元素为止 . 要删除的元素的确切索引由公式 (permNumber % factorial(arr.length)) / factorial(arr.length-1) 给出 . 其他公式可用于确定要删除的索引，只要它保留数字和排列之间的一对一映射即可 .

Example

以下是如何为数组 (a,b,c,d) 生成所有排列：

#    Perm      1st El        2nd El      3rd El    4th El
0    abcd   (a,b,c,d)[0]   (b,c,d)[0]   (c,d)[0]   (d)[0]
1    abdc   (a,b,c,d)[0]   (b,c,d)[0]   (c,d)[1]   (c)[0]
2    acbd   (a,b,c,d)[0]   (b,c,d)[1]   (b,d)[0]   (d)[0]
3    acdb   (a,b,c,d)[0]   (b,c,d)[1]   (b,d)[1]   (b)[0]
4    adbc   (a,b,c,d)[0]   (b,c,d)[2]   (b,c)[0]   (c)[0]
5    adcb   (a,b,c,d)[0]   (b,c,d)[2]   (b,c)[1]   (b)[0]
6    bacd   (a,b,c,d)[1]   (a,c,d)[0]   (c,d)[0]   (d)[0]
7    badc   (a,b,c,d)[1]   (a,c,d)[0]   (c,d)[1]   (c)[0]
8    bcad   (a,b,c,d)[1]   (a,c,d)[1]   (a,d)[0]   (d)[0]
9    bcda   (a,b,c,d)[1]   (a,c,d)[1]   (a,d)[1]   (a)[0]
10   bdac   (a,b,c,d)[1]   (a,c,d)[2]   (a,c)[0]   (c)[0]
11   bdca   (a,b,c,d)[1]   (a,c,d)[2]   (a,c)[1]   (a)[0]
12   cabd   (a,b,c,d)[2]   (a,b,d)[0]   (b,d)[0]   (d)[0]
13   cadb   (a,b,c,d)[2]   (a,b,d)[0]   (b,d)[1]   (b)[0]
14   cbad   (a,b,c,d)[2]   (a,b,d)[1]   (a,d)[0]   (d)[0]
15   cbda   (a,b,c,d)[2]   (a,b,d)[1]   (a,d)[1]   (a)[0]
16   cdab   (a,b,c,d)[2]   (a,b,d)[2]   (a,b)[0]   (b)[0]
17   cdba   (a,b,c,d)[2]   (a,b,d)[2]   (a,b)[1]   (a)[0]
18   dabc   (a,b,c,d)[3]   (a,b,c)[0]   (b,c)[0]   (c)[0]
19   dacb   (a,b,c,d)[3]   (a,b,c)[0]   (b,c)[1]   (b)[0]
20   dbac   (a,b,c,d)[3]   (a,b,c)[1]   (a,c)[0]   (c)[0]
21   dbca   (a,b,c,d)[3]   (a,b,c)[1]   (a,c)[1]   (a)[0]
22   dcab   (a,b,c,d)[3]   (a,b,c)[2]   (a,b)[0]   (b)[0]
23   dcba   (a,b,c,d)[3]   (a,b,c)[2]   (a,b)[1]   (a)[0]

请注意，每个排列＃的形式如下：

(firstElIndex * 3!) + (secondElIndex * 2!) + (thirdElIndex * 1!) + (fourthElIndex * 0!)

这基本上是解释中给出的公式的逆过程 .

回复于 2024-04-19T00:36:22+08:00

3
我敢于添加另一个答案，旨在回答你关于 slice ， concat ， reverse 的问题 .

答案是（几乎）可能，但它不会很有效 . 您在算法中执行的操作如下：
- 在排列数组中找到第一个反转，从右到左（在这种情况下反转定义为 i 和 j ，其中 i < j 和 perm[i] > perm[j] ，从左到右给出的指数
- 放置较大的反转次数
- 以相反的顺序连接处理后的数字，这与排序顺序相同，因为没有观察到反转 .
- 连接倒数的第二个数字（仍然按照previos数字排序，因为没有观察到反转）
这主要是我的第一个答案，但是以更优化的方式 .

Example

考虑排列9,10,11,8,7,6,5,4,3,2,1从右到左的第一个反演是10,11 . 实际上下一个排列是：9,11,1， 2,3,4,5,6,7,8,9,10 = 9concat（11）的concat（REV（8,7,6,5,4,3,2,1））的concat（10）

Source code 这里我包含了我想象的源代码：
```
var nextPermutation = function(arr) {
  for (var i = arr.length - 2; i >= 0; i--) {
     if (arr[i] < arr[i + 1]) {
        return arr.slice(0, i).concat([arr[i + 1]]).concat(arr.slice(i + 2).reverse()).concat([arr[i]]);
     }
  }
  // return again the first permutation if calling next permutation on last.
  return arr.reverse();
}

console.log(nextPermutation([9, 10, 11, 8, 7, 6, 5, 4, 3, 2, 1]));
console.log(nextPermutation([6, 5, 4, 3, 2, 1]));
console.log(nextPermutation([1, 2, 3, 4, 5, 6]));
```
代码可用于jsfiddle here .
回复于 2024-04-19T00:36:22+08:00

一个相当简单的C代码，没有递归 .

#include <vector>
#include <algorithm>
#include <iterator>
#include <iostream>
#include <string>

// Integer data
void print_all_permutations(std::vector<int> &data) {
    std::stable_sort(std::begin(data), std::end(data));
    do {
        std::copy(data.begin(), data.end(), std::ostream_iterator<int>(std::cout, " ")), std::cout << '\n';
    } while (std::next_permutation(std::begin(data), std::end(data)));
}

// Character data (string)
void print_all_permutations(std::string &data) {
    std::stable_sort(std::begin(data), std::end(data));
    do {
        std::copy(data.begin(), data.end(), std::ostream_iterator<char>(std::cout, " ")), std::cout << '\n';
    } while (std::next_permutation(std::begin(data), std::end(data)));
}

int main()
{
    std::vector<int> v({1,2,3,4});
    print_all_permutations(v);

    std::string s("abcd");
    print_all_permutations(s);

    return 0;
}

我们可以在线性时间内找到序列的下一个排列 .

回复于 2024-04-19T00:36:22+08:00

Here is an answer from @le_m . 它可能会有所帮助 .

以下非常有效的算法使用Heap的方法生成N个元素的所有排列，运行时复杂度为O（N！）：

function permute(permutation) {
  var length = permutation.length,
      result = [permutation.slice()],
      c = new Array(length).fill(0),
      i = 1, k, p;

  while (i < length) {
    if (c[i] < i) {
      k = i % 2 && c[i];
      p = permutation[i];
      permutation[i] = permutation[k];
      permutation[k] = p;
      ++c[i];
      i = 1;
      result.push(permutation.slice());
    } else {
      c[i] = 0;
      ++i;
    }
  }
  return result;
}

console.log(JSON.stringify(permute([1, 2, 3, 4])));

回复于 2024-04-19T00:36:22+08:00

没有递归函数调用的排列

8 回答

相关问题