在序列的所有配对上测试对称函数的有效方法

Question

假设我有一个像[ "a"; "b"; "c" ]这样的集合，并且我想针对每个其他元素测试每个元素。

我可以生成这样的所有配对：

let combinations xs = 
Seq.allPairs xs xs 
|> Seq.filter (fun (x, y) -> x <> y) 
|> Seq.toList
combinations [ "a"; "b"; "c" ] 
// [("a", "b"); ("a", "c"); ("b", "a"); ("b", "c"); ("c", "a"); ("c", "b")]

但对于我的测试，我总是知道f x y = f y x(因为f是对称的(，所以我想减少测试的组合数量：

let combinations xs = 
Seq.allPairs xs xs 
|> Seq.filter (fun (x, y) -> x <> y && x < y) 
|> Seq.toList
combinations [ "a"; "b"; "c" ] 
// [("a", "b"); ("a", "c"); ("b", "c")]

但是这个：

1. 似乎不是生成测试用例的有效方法
2. 需要x : comparison，我认为没有必要

我应该如何在F#中实现这一点？

Answer 1

不知道高效-这看起来像是你需要缓存已经生成的对，并根据它们在缓存中的存在进行过滤。

Seq.allPairs的库实现遵循以下路线：

let allPairs source1 source2 =
source1 |> Seq.collect (fun x -> source2 |> Seq.map (fun y -> x, y))
// val allPairs : source1:seq<'a> -> source2:seq<'b> -> seq<'a * 'b>

然后将缓存和过滤集成到其中，将两个序列约束为类型seq<'a>并引入equality约束。

let allPairs1 source1 source2 =
let h = System.Collections.Generic.HashSet()
source1 |> Seq.collect (fun x -> 
source2 |> Seq.choose (fun y -> 
if x = y || h.Contains (x, y) || h.Contains (y, x) then None
else h.Add (x, y) |> ignore; Some (x, y) ) )
// val allPairs1 :
//     source1:seq<'a> -> source2:seq<'a> -> seq<'a * 'a> when 'a : equality

测试

allPairs1 [1..3] [2..4] |> Seq.toList
// val it : (int * int) list = [(1, 2); (1, 3); (1, 4); (2, 3); (2, 4); (3, 4)]

Answer 2

因为f是可交换的，所以获得所有组合的最简单方法是将每个项与列表的其余项投影到一对中。

let rec combinations = function
| [] -> []
| x::xs -> (xs |> List.map (fun y -> (x, y))) @ (combinations xs)

我们不需要任何比较约束。

let xs = [1; 2; 3; 4;]
combinations xs // [(1, 2); (1, 3); (1, 4); (2, 3); (2, 4); (3, 4)]

使用@kaefer的方法检查结果：

combinations xs = (allPairs1 xs xs |> Seq.toList) // true

Answer 3

另一个假设所有元素都不同的解决方案(它使用位置作为标识(：

let allSymmetricPairs xs =
seq {
let xs = Seq.toArray xs
for i = 0 to Array.length xs - 2 do
for j = i + 1 to Array.length xs - 1 do
yield xs.[i], xs.[j]
}

我们还可以预先分配阵列，如果您计划提取整个序列，这可能会更快：

let allSymmetricPairs xs =
let xs = Seq.toArray xs
let n = Array.length xs
let result = Array.zeroCreate (n * (n - 1) / 2)
let mutable k = 0
for i = 0 to n - 2 do
for j = i + 1 to n - 1 do
result.[k] <- xs.[i], xs.[j]
k <- k + 1
result