时间戳

首页 > 解决方案 > 在 Seq 的所有配对上测试对称函数的有效方法

f# - 在 Seq 的所有配对上测试对称函数的有效方法

问题描述

假设我有一个类似的集合，[ "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# 中实现它？

标签： f#

解决方案

不知道效率 - 这看起来你需要缓存已经生成的对并过滤它们在缓存中的存在。

的库实现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)]

推荐阅读