在 F# 中计算排列 [英] Calculating permutations in F#

问题描述

受到这个问题和答案，如何创建通用排列算法在 F# 中?Google 没有对此提供任何有用的答案.

Inspired by this question and answer, how do I create a generic permutations algorithm in F#? Google doesn't give any useful answers to this.

我在下面提供了我的最佳答案，但我怀疑 Tomas 的更好(当然更短！)

I provide my best answer below, but I suspect that Tomas's is better (certainly shorter!)

推荐答案

你也可以这样写:

let rec permutations list taken = 
  seq { if Set.count taken = List.length list then yield [] else
        for l in list do
          if not (Set.contains l taken) then 
            for perm in permutations list (Set.add l taken)  do
              yield l::perm }

'list' 参数包含您想要置换的所有数字，而 'taken' 是一个包含已使用数字的集合.当所有数字都被占用时，该函数返回空列表.否则，它会遍历所有仍然可用的数字，获取剩余数字的所有可能排列(递归使用排列")并在返回之前将当前数字附加到每个数字上 (l::perm).

The 'list' argument contains all the numbers that you want to permute and 'taken' is a set that contains numbers already used. The function returns empty list when all numbers all taken. Otherwise, it iterates over all numbers that are still available, gets all possible permutations of the remaining numbers (recursively using 'permutations') and appends the current number to each of them before returning (l::perm).

要运行这个，你需要给它一个空集，因为一开始没有使用数字:

To run this, you'll give it an empty set, because no numbers are used at the beginning:

permutations [1;2;3] Set.empty;;

这篇关于在 F# 中计算排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！