IT技术 - JavaScript 中的排列？ - 吾爱随笔录

JavaScript 中的排列？

IT技术 javascript permutation

2021-02-02 01:16:16

我正在尝试编写一个执行以下操作的函数：

将整数数组作为参数（例如 [1,2,3,4]）
创建一个包含 [1,2,3,4] 的所有可能排列的数组，每个排列的长度为 4

下面的函数（我在网上找到它）通过将字符串作为参数并返回该字符串的所有排列来完成此操作

我不知道如何修改它以使其适用于整数数组，（我认为这与某些方法在字符串上的工作方式与在整数上的工作方式不同有关，但我不确定。 ..)

var permArr = [], usedChars = [];
function permute(input) {
  var i, ch, chars = input.split("");
  for (i = 0; i < chars.length; i++) {
    ch = chars.splice(i, 1);
    usedChars.push(ch);
    if (chars.length == 0)
      permArr[permArr.length] = usedChars.join("");
    permute(chars.join(""));
    chars.splice(i, 0, ch);
    usedChars.pop();
  }
  return permArr
};

注意：我希望函数返回整数数组，而不是字符串数组。

我真的需要 JavaScript 的解决方案。我已经想出了如何在 python 中做到这一点

6个回答

有点晚了，但想在这里添加一个稍微优雅的版本。可以是任何数组...

function permutator(inputArr) {
  var results = [];

  function permute(arr, memo) {
    var cur, memo = memo || [];

    for (var i = 0; i < arr.length; i++) {
      cur = arr.splice(i, 1);
      if (arr.length === 0) {
        results.push(memo.concat(cur));
      }
      permute(arr.slice(), memo.concat(cur));
      arr.splice(i, 0, cur[0]);
    }

    return results;
  }

  return permute(inputArr);
}

添加 ES6 (2015) 版本。也不会改变原始输入数组。在 Chrome 的控制台中工作...

const permutator = (inputArr) => {
  let result = [];

  const permute = (arr, m = []) => {
    if (arr.length === 0) {
      result.push(m)
    } else {
      for (let i = 0; i < arr.length; i++) {
        let curr = arr.slice();
        let next = curr.splice(i, 1);
        permute(curr.slice(), m.concat(next))
     }
   }
 }

 permute(inputArr)

 return result;
}

所以...

permutator(['c','a','t']);

产量...

[ [ 'c', 'a', 't' ],
  [ 'c', 't', 'a' ],
  [ 'a', 'c', 't' ],
  [ 'a', 't', 'c' ],
  [ 't', 'c', 'a' ],
  [ 't', 'a', 'c' ] ]

和...

permutator([1,2,3]);

产量...

[ [ 1, 2, 3 ],
  [ 1, 3, 2 ],
  [ 2, 1, 3 ],
  [ 2, 3, 1 ],
  [ 3, 1, 2 ],
  [ 3, 2, 1 ] ]

我们如何设置排列的长度？

2021-03-19 01:16:16

线有var cur, memo = memo || [];什么作用？

2021-03-22 01:16:16

如果您有一个方便的阶乘函数（考虑到您很可能正在处理排列），您可以通过将外部作用域初始化更改为来加速它 var results = new Array(factorial(inputArr.length)), length=0，然后替换results.push(…)为results[length++]=…

2021-03-30 01:16:16

@user2965967 声明了cur 和memo，并且将memo 初始化为memo 的值，除非它是falsey（包括undefined），在这种情况下它将是一个空数组。换句话说，为函数参数提供默认值是一种不太理想的方式。

2021-04-02 01:16:16

是slice()在permute(curr.slice(), m.concat(next))真的有必要吗？

2021-04-03 01:16:16

如果您注意到，代码实际上在进行任何排列之前将字符拆分为一个数组，因此您只需删除连接和拆分操作

var permArr = [],
  usedChars = [];

function permute(input) {
  var i, ch;
  for (i = 0; i < input.length; i++) {
    ch = input.splice(i, 1)[0];
    usedChars.push(ch);
    if (input.length == 0) {
      permArr.push(usedChars.slice());
    }
    permute(input);
    input.splice(i, 0, ch);
    usedChars.pop();
  }
  return permArr
};


document.write(JSON.stringify(permute([5, 3, 7, 1])));

有一个关于这个答案的新问题。

2021-03-12 01:16:16

@思干腾。我在尝试使用您的功能时发生了一些奇怪的事情。我把它保存在一个 .js 中，在那里我有我所有的“列表操作功能”。如果我将它与 permute([1,2,3]) 和后来的 permute([4,5,6]) 一起使用，则后者的输出仍然具有结果，即第一个的输出。知道如何解决这个问题吗？非常感谢！

2021-03-28 01:16:16

在你的函数中访问全局变量，错误的形式！

2021-04-05 01:16:16

以下非常有效的算法使用Heap 的方法生成运行时复杂度为 O(N!) 的 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(permute([1, 2, 3]));

作为空间复杂度为 O(N)的生成器实现的相同算法：

Show code snippet

function* permute(permutation) {
  var length = permutation.length,
      c = Array(length).fill(0),
      i = 1, k, p;

  yield permutation.slice();
  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;
      yield permutation.slice();
    } else {
      c[i] = 0;
      ++i;
    }
  }
}

// Memory efficient iteration through permutations:
for (var permutation of permute([1, 2, 3])) console.log(permutation);

// Simple array conversion:
var permutations = [...permute([1, 2, 3])];

性能对比

随意将您的实现添加到以下benchmark.js测试套件中：

Show code snippet

function permute_SiGanteng(input) {
  var permArr = [],
    usedChars = [];

  function permute(input) {
    var i, ch;
    for (i = 0; i < input.length; i++) {
      ch = input.splice(i, 1)[0];
      usedChars.push(ch);
      if (input.length == 0) {
        permArr.push(usedChars.slice());
      }
      permute(input);
      input.splice(i, 0, ch);
      usedChars.pop();
    }
    return permArr
  }
  return permute(input);
}

function permute_delimited(inputArr) {
  var results = [];

  function permute(arr, memo) {
    var cur, memo = memo || [];
    for (var i = 0; i < arr.length; i++) {
      cur = arr.splice(i, 1);
      if (arr.length === 0) {
        results.push(memo.concat(cur));
      }
      permute(arr.slice(), memo.concat(cur));
      arr.splice(i, 0, cur[0]);
    }
    return results;
  }
  return permute(inputArr);
}

function permute_monkey(inputArray) {
  return inputArray.reduce(function permute(res, item, key, arr) {
    return res.concat(arr.length > 1 && arr.slice(0, key).concat(arr.slice(key + 1)).reduce(permute, []).map(function(perm) {
      return [item].concat(perm);
    }) || item);
  }, []);
}

function permute_Oriol(input) {
  var permArr = [],
    usedChars = [];
  return (function main() {
    for (var i = 0; i < input.length; i++) {
      var ch = input.splice(i, 1)[0];
      usedChars.push(ch);
      if (input.length == 0) {
        permArr.push(usedChars.slice());
      }
      main();
      input.splice(i, 0, ch);
      usedChars.pop();
    }
    return permArr;
  })();
}

function permute_MarkusT(input) {
  function permutate(array, callback) {
      function p(array, index, callback) {
          function swap(a, i1, i2) {
              var t = a[i1];
              a[i1] = a[i2];
              a[i2] = t;
          }
          if (index == array.length - 1) {
              callback(array);
              return 1;
          } else {
              var count = p(array, index + 1, callback);
              for (var i = index + 1; i < array.length; i++) {
                  swap(array, i, index);
                  count += p(array, index + 1, callback);
                  swap(array, i, index);
              }
              return count;
          }
      }
      if (!array || array.length == 0) {
          return 0;
      }
      return p(array, 0, callback);
  }
  var result = [];
  permutate(input, function(a) {
      result.push(a.slice(0));
  });
  return result;
}

function permute_le_m(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;
}

function permute_Urielzen(arr) {
    var finalArr = [];
    var iterator = function (arrayTaken, tree) {
        for (var i = 0; i < tree; i++) {
            var temp = arrayTaken.slice();
            temp.splice(tree - 1 - i, 0, temp.splice(tree - 1, 1)[0]);
            if (tree >= arr.length) {
                finalArr.push(temp);
            } else { iterator(temp, tree + 1); }
        }
    }
    iterator(arr, 1); return finalArr;
}

function permute_Taylor_Hakes(arr) {
  var permutations = [];
  if (arr.length === 1) {
    return [ arr ];
  }

  for (var i = 0; i <  arr.length; i++) { 
    var subPerms = permute_Taylor_Hakes(arr.slice(0, i).concat(arr.slice(i + 1)));
    for (var j = 0; j < subPerms.length; j++) {
      subPerms[j].unshift(arr[i]);
      permutations.push(subPerms[j]);
    }
  }
  return permutations;
}

var Combinatorics = (function () {
    'use strict';
    var version = "0.5.2";
    /* combinatory arithmetics */
    var P = function(m, n) {
        var p = 1;
        while (n--) p *= m--;
        return p;
    };
    var C = function(m, n) {
        if (n > m) {
            return 0;
        }
        return P(m, n) / P(n, n);
    };
    var factorial = function(n) {
        return P(n, n);
    };
    var factoradic = function(n, d) {
        var f = 1;
        if (!d) {
            for (d = 1; f < n; f *= ++d);
            if (f > n) f /= d--;
        } else {
            f = factorial(d);
        }
        var result = [0];
        for (; d; f /= d--) {
            result[d] = Math.floor(n / f);
            n %= f;
        }
        return result;
    };
    /* common methods */
    var addProperties = function(dst, src) {
        Object.keys(src).forEach(function(p) {
            Object.defineProperty(dst, p, {
                value: src[p],
                configurable: p == 'next'
            });
        });
    };
    var hideProperty = function(o, p) {
        Object.defineProperty(o, p, {
            writable: true
        });
    };
    var toArray = function(f) {
        var e, result = [];
        this.init();
        while (e = this.next()) result.push(f ? f(e) : e);
        this.init();
        return result;
    };
    var common = {
        toArray: toArray,
        map: toArray,
        forEach: function(f) {
            var e;
            this.init();
            while (e = this.next()) f(e);
            this.init();
        },
        filter: function(f) {
            var e, result = [];
            this.init();
            while (e = this.next()) if (f(e)) result.push(e);
            this.init();
            return result;
        },
        lazyMap: function(f) {
            this._lazyMap = f;
            return this;
        },
        lazyFilter: function(f) {
            Object.defineProperty(this, 'next', {
                writable: true
            });
            if (typeof f !== 'function') {
                this.next = this._next;
            } else {
                if (typeof (this._next) !== 'function') {
                    this._next = this.next;
                }
                var _next = this._next.bind(this);
                this.next = (function() {
                    var e;
                    while (e = _next()) {
                        if (f(e))
                            return e;
                    }
                    return e;
                }).bind(this);
            }
            Object.defineProperty(this, 'next', {
                writable: false
            });
            return this;
        }

    };
    /* power set */
    var power = function(ary, fun) {
        var size = 1 << ary.length,
            sizeOf = function() {
                return size;
            },
            that = Object.create(ary.slice(), {
                length: {
                    get: sizeOf
                }
            });
        hideProperty(that, 'index');
        addProperties(that, {
            valueOf: sizeOf,
            init: function() {
                that.index = 0;
            },
            nth: function(n) {
                if (n >= size) return;
                var i = 0,
                    result = [];
                for (; n; n >>>= 1, i++) if (n & 1) result.push(this[i]);
                return (typeof (that._lazyMap) === 'function')?that._lazyMap(result):result;
            },
            next: function() {
                return this.nth(this.index++);
            }
        });
        addProperties(that, common);
        that.init();
        return (typeof (fun) === 'function') ? that.map(fun) : that;
    };
    /* combination */
    var nextIndex = function(n) {
        var smallest = n & -n,
            ripple = n + smallest,
            new_smallest = ripple & -ripple,
            ones = ((new_smallest / smallest) >> 1) - 1;
        return ripple | ones;
    };
    var combination = function(ary, nelem, fun) {
        if (!nelem) nelem = ary.length;
        if (nelem < 1) throw new RangeError;
        if (nelem > ary.length) throw new RangeError;
        var first = (1 << nelem) - 1,
            size = C(ary.length, nelem),
            maxIndex = 1 << ary.length,
            sizeOf = function() {
                return size;
            },
            that = Object.create(ary.slice(), {
                length: {
                    get: sizeOf
                }
            });
        hideProperty(that, 'index');
        addProperties(that, {
            valueOf: sizeOf,
            init: function() {
                this.index = first;
            },
            next: function() {
                if (this.index >= maxIndex) return;
                var i = 0,
                    n = this.index,
                    result = [];
                for (; n; n >>>= 1, i++) {
                    if (n & 1) result[result.length] = this[i];
                }

                this.index = nextIndex(this.index);
                return (typeof (that._lazyMap) === 'function')?that._lazyMap(result):result;
            }
        });
        addProperties(that, common);
        that.init();
        return (typeof (fun) === 'function') ? that.map(fun) : that;
    };
    /* permutation */
    var _permutation = function(ary) {
        var that = ary.slice(),
            size = factorial(that.length);
        that.index = 0;
        that.next = function() {
            if (this.index >= size) return;
            var copy = this.slice(),
                digits = factoradic(this.index, this.length),
                result = [],
                i = this.length - 1;
            for (; i >= 0; --i) result.push(copy.splice(digits[i], 1)[0]);
            this.index++;
            return (typeof (that._lazyMap) === 'function')?that._lazyMap(result):result;
        };
        return that;
    };
    // which is really a permutation of combination
    var permutation = function(ary, nelem, fun) {
        if (!nelem) nelem = ary.length;
        if (nelem < 1) throw new RangeError;
        if (nelem > ary.length) throw new RangeError;
        var size = P(ary.length, nelem),
            sizeOf = function() {
                return size;
            },
            that = Object.create(ary.slice(), {
                length: {
                    get: sizeOf
                }
            });
        hideProperty(that, 'cmb');
        hideProperty(that, 'per');
        addProperties(that, {
            valueOf: function() {
                return size;
            },
            init: function() {
                this.cmb = combination(ary, nelem);
                this.per = _permutation(this.cmb.next());
            },
            next: function() {
                var result = this.per.next();
                if (!result) {
                    var cmb = this.cmb.next();
                    if (!cmb) return;
                    this.per = _permutation(cmb);
                    return this.next();
                }
                return (typeof (that._lazyMap) === 'function')?that._lazyMap(result):result;
            }
        });
        addProperties(that, common);
        that.init();
        return (typeof (fun) === 'function') ? that.map(fun) : that;
    };

    /* export */
    var Combinatorics = Object.create(null);
    addProperties(Combinatorics, {
        C: C,
        P: P,
        factorial: factorial,
        factoradic: factoradic,
        permutation: permutation,
    });
    return Combinatorics;
})();

function permute_Technicalbloke(inputArray) {
  if (inputArray.length === 1) return inputArray;
  return inputArray.reduce( function(accumulator,_,index){
    permute_Technicalbloke([...inputArray.slice(0,index),...inputArray.slice(index+1)])
    .map(value=>accumulator.push([inputArray[index],value]));
    return accumulator;
  },[]);
}

var suite = new Benchmark.Suite;
var input = [0, 1, 2, 3, 4];

suite.add('permute_SiGanteng', function() {
    permute_SiGanteng(input);
  })
  .add('permute_delimited', function() {
    permute_delimited(input);
  })
  .add('permute_monkey', function() {
    permute_monkey(input);
  })
  .add('permute_Oriol', function() {
    permute_Oriol(input);
  })
  .add('permute_MarkusT', function() {
    permute_MarkusT(input);
  })
  .add('permute_le_m', function() {
    permute_le_m(input);
  })
  .add('permute_Urielzen', function() {
    permute_Urielzen(input);
  })
  .add('permute_Taylor_Hakes', function() {
    permute_Taylor_Hakes(input);
  })
  .add('permute_Combinatorics', function() {
    Combinatorics.permutation(input).toArray();
  })
  .add('permute_Technicalbloke', function() {
    permute_Technicalbloke(input);
  })
  .on('cycle', function(event) {
    console.log(String(event.target));
  })
  .on('complete', function() {
    console.log('Fastest is ' + this.filter('fastest').map('name'));
  })
  .run({async: true});

<script src="https://cdnjs.cloudflare.com/ajax/libs/lodash.js/4.17.4/lodash.min.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/platform/1.3.4/platform.min.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/benchmark/2.1.4/benchmark.min.js"></script>

Chrome 48 的运行时结果：

99.152ms这个算法
153.115毫秒
401.255ms js 组合
497.037毫秒
925.669ms奥里奥尔
1026.571ms四干腾
2529.841ms分隔
3992.622ms猴子
4514.665ms Oriol

如何更改此代码以提供固定 n = 2 的结果？例如，假设我们有一组三个字母：A、B 和 C。我们可能会问有多少种方法可以排列该组中的 2 个字母。每个可能的排列都是排列的一个例子。可能排列的完整列表是：AB、AC、BA、BC、CA 和 CB。

2021-03-15 01:16:16

@a4xrbj1 我将使用与上面给出的链接类似的策略（另请参阅stackoverflow.com/questions/127704/...）计算固定长度 n（例如 AB、AC、BC for n = 2）的所有组合，然后计算每个组合使用堆的方法计算它的所有排列。当然可以优化特殊情况，例如 n = 2。

2021-03-21 01:16:16

@le_m 是的，特别是使用这个（堆的）方法，因为它太快了

2021-03-26 01:16:16

@a4xrbj1 参见例如这个问题中的代码示例： stackoverflow.com/questions/37892738/... - 或者你是专门询问修改这个（堆的）方法？

2021-04-01 01:16:16

生成器版本无法正常工作，yield permutation.slice()如果您不切片，您应该这样做，您只会计算最后一个排列。

2021-04-03 01:16:16

var inputArray = [1, 2, 3];

var result = inputArray.reduce(function permute(res, item, key, arr) {
    return res.concat(arr.length > 1 && arr.slice(0, key).concat(arr.slice(key + 1)).reduce(permute, []).map(function(perm) { return [item].concat(perm); }) || item);
}, []);


alert(JSON.stringify(result));

是否有与该概念平行的 lisp[1,2,3].length == 3 && "foo" || "bar"或[1,2].length == 3 && "foo" || "bar"哦，天哪！有！(or (and (= 3 2) (print "hello!")) (print "goodbye"))

2021-03-10 01:16:16

哇，尽管它简洁且缺乏文档，但我认为这是最优雅的答案。我对这个算法的解释是：对于数组中的每个项目（减少），选择所有其他项目，排列它们（递归），并连接到这个项目。

2021-03-19 01:16:16

@lolmaus-AndreyMikhaylov 如何删除重复项，如果可以，请更新答案

2021-03-19 01:16:16

在此处尝试了此解决方案：codewars.com/kata/reviews/5254ca2719453dcc0b000280/groups/...我已将原始高尔夫代码展开为可读的代码，但本质上是相同的。它的问题在于它会产生重复项，我不得不对结果做额外的.filter(uniq)处理。

2021-03-25 01:16:16

如果它甚至不可读，它怎么能优雅。这是一个简单的修复，我建议进行编辑。

2021-03-26 01:16:16

我改进了司干腾的回答。

现在可以permute多次调用，因为permArr和usedChars每次都被清除。

function permute(input) {
    var permArr = [],
        usedChars = [];
    return (function main() {
        for (var i = 0; i < input.length; i++) {
            var ch = input.splice(i, 1)[0];
            usedChars.push(ch);
            if (input.length == 0) {
                permArr.push(usedChars.slice());
            }
            main();
            input.splice(i, 0, ch);
            usedChars.pop();
        }
        return permArr;
    })();
}

Show code snippet

function permute(input) {
  var permArr = [],
      usedChars = [];
  return (function main() {
    for (var i = 0; i < input.length; i++) {
      var ch = input.splice(i, 1)[0];
      usedChars.push(ch);
      if (input.length == 0) {
        permArr.push(usedChars.slice());
      }
      main();
      input.splice(i, 0, ch);
      usedChars.pop();
    }
    return permArr;
  })();
}
document.write(JSON.stringify(permute([5, 3, 7, 1])));

其它你可能感兴趣的问题

上一篇一个接一个地（即按顺序）解决Promise？下一篇Chrome 扩展消息传递：未发送响应