Clojure의 test.check에서 임의의 서브 시퀀스를 어떻게 샘플링합니까?

Question

Subset Sum Problem의 임의의 해결할 수있는 인스턴스를 생성하려고합니다. Wikipedia는 목표 값이 항상 0이어야한다고 말하지만 목표 값을 지정할 수도 있습니다. 이는 내가 여기서하고있는 것입니다.

따라서 (gen/vector gen/int)을 사용하여 임의의 벡터를 만든 다음 임의의 하위 벡터를 샘플링하고 그 벡터의 합계를 사용하여 대상 값을 만듭니다. gen/elements을 사용하는 명백한 전략의 문제점은 동일한 요소를 반복적으로 샘플링 할 수 있다는 것입니다.
다음으로 가장 좋은 아이디어는 임의의 색인 집합을 만들어 해당 색인의 모든 요소를 ​​추출하는 것입니다. 더 간단한 접근법이 있습니까?

Answer 1

This generator (test.chuck)은 각 요소에 대해 포함 플래그를 생성하여 요청한 작업을 수행합니다.

Answer 2

이 코드는 내가 생각하는 것의 모형입니다. 정수의 벡터를 생성합니다. 각 벡터에는 그것이 하위 집합에 속하는지 여부를 나타내는 플래그가 있습니다 (소수, 일부 또는 모두 일 수 있음). 더미 함수 (부분 집합 합계)는 테스트가 통과하는지 여부를 결정합니다. project.clj에 [tupelo "0.9.56"]이 필요합니다.

(ns tst.demo.core 
    (:require 
    [clojure.test.check :as tc] 
    [clojure.test.check.generators :as tcgen] 
    [clojure.test.check.properties :as tcprop] 
    [tupelo.core :as t] 
    [tupelo.test :as tt] 
    [schema.core :as s])) 

(def IntBoolTuple [ (s/one s/Int "x1") (s/one s/Bool "x2") ]) 

(s/defn is-sum-tuple? :- s/Bool 
    [tuple :- IntBoolTuple] 
    (let [[int-val bool-val] tuple] 
    bool-val)) 

(s/defn tst-fn :- s/Bool 
    "Dummy test function" 
    [tuples :- [IntBoolTuple]] 
    (let [all-ints  (mapv first tuples) 
     flags   (mapv second tuples) 
     tuples-to-add (vec (filter is-sum-tuple? tuples)) 
     ints-to-add (mapv first tuples-to-add) 
     int-sum  (apply + ints-to-add)] 
    (< -20 int-sum))) ; dummy test: pass if not too negative 

(tt/dospec 999 
    (tcprop/for-all [tuples (tcgen/such-that 
          (fn st-fn [tuples] (pos? (count tuples))) ; ensure at least 1 tuple is present 
          (tcgen/vector ; 0 or more tuples, ex: [ [5 false] [2 true] ...] 
           (tcgen/tuple tcgen/int tcgen/boolean) ; a tuple like [5 false] 
          ))] 
    (t/spyx tuples) ; display 
    (tst-fn tuples))) 

위의 코드는 다음과 같은 출력을 생성

--------------------------------------- 
    Clojure 1.9.0-beta1 Java 9.0.1 
--------------------------------------- 

Testing tst.demo.core 
tuples => [[-1 false]] 
tuples => [[1 true]] 
tuples => [[-2 true] [-1 false]] 
tuples => [[3 true] [-1 true]] 
tuples => [[1 true]] 
tuples => [[-1 true] [5 true] [-4 true] [5 false]] 
tuples => [[5 true] [2 false] [3 false] [1 true] [0 true]] 
tuples => [[2 false] [-4 false]] 
tuples => [[2 false]] 
tuples => [[2 false] [8 true] [9 true] [9 true] [3 true] [-7 true] [-9 true] [8 false] [-9 true]] 
tuples => [[-9 true] [-1 true]] 
tuples => [[4 false] [-6 true] [0 false] [10 true]] 
tuples => [[-2 false] [7 true] [-12 false] [4 false] [4 false] [11 true] [6 false] [-5 false]] 
tuples => [[-5 false] [6 true] [9 true] [-7 true] [1 false] [3 false] [-9 true] [-9 true] [-8 true] [-8 false] [-12 false]] 
tuples => [[-7 false] [-14 false] [8 false] [-1 false] [-14 true] [-10 false] [-8 true] [1 false] [5 false] [-13 true]] 
tuples => [[-14 false] [8 false] [-1 false] [-14 true] [-10 false] [-8 true] [1 false] [5 false] [-13 true]] 
tuples => [[-7 false] [8 false] [-1 false] [-14 true] [-10 false] [-8 true] [1 false] [5 false] [-13 true]] 
tuples => [[-7 false] [-14 false] [-1 false] [-14 true] [-10 false] [-8 true] [1 false] [5 false] [-13 true]] 
tuples => [[-7 false] [-14 false] [8 false] [-14 true] [-10 false] [-8 true] [1 false] [5 false] [-13 true]] 
tuples => [[-7 false] [-14 false] [8 false] [-1 false] [-10 false] [-8 true] [1 false] [5 false] [-13 true]] 
tuples => [[-7 false] [-14 false] [8 false] [-1 false] [-14 true] [-8 true] [1 false] [5 false] [-13 true]] 
tuples => [[-7 false] [-14 false] [8 false] [-1 false] [-14 true] [-10 false] [1 false] [5 false] [-13 true]] 
tuples => [[-7 false] [-14 false] [8 false] [-1 false] [-14 true] [-10 false] [-8 true] [5 false] [-13 true]] 
tuples => [[-7 false] [-14 false] [8 false] [-1 false] [-14 true] [-10 false] [-8 true] [1 false] [-13 true]] 
tuples => [[-7 false] [-14 false] [8 false] [-1 false] [-14 true] [-10 false] [-8 true] [1 false] [5 false]] 
tuples => [[8 false] [-1 false] [-14 true] [-10 false] [-8 true] [1 false] [5 false] [-13 true]] 
tuples => [[-14 false] [-1 false] [-14 true] [-10 false] [-8 true] [1 false] [5 false] [-13 true]] 
tuples => [[-14 false] [8 false] [-14 true] [-10 false] [-8 true] [1 false] [5 false] [-13 true]] 
tuples => [[-14 false] [8 false] [-1 false] [-10 false] [-8 true] [1 false] [5 false] [-13 true]] 
tuples => [[-14 false] [8 false] [-1 false] [-14 true] [-8 true] [1 false] [5 false] [-13 true]] 
tuples => [[-14 false] [8 false] [-1 false] [-14 true] [-10 false] [1 false] [5 false] [-13 true]] 
tuples => [[-14 false] [8 false] [-1 false] [-14 true] [-10 false] [-8 true] [5 false] [-13 true]] 
tuples => [[-14 false] [8 false] [-1 false] [-14 true] [-10 false] [-8 true] [1 false] [-13 true]] 
tuples => [[-14 false] [8 false] [-1 false] [-14 true] [-10 false] [-8 true] [1 false] [5 false]] 
tuples => [[-1 false] [-14 true] [-10 false] [-8 true] [1 false] [5 false] [-13 true]] 
tuples => [[8 false] [-14 true] [-10 false] [-8 true] [1 false] [5 false] [-13 true]] 
tuples => [[8 false] [-1 false] [-10 false] [-8 true] [1 false] [5 false] [-13 true]] 
tuples => [[8 false] [-1 false] [-14 true] [-8 true] [1 false] [5 false] [-13 true]] 
tuples => [[8 false] [-1 false] [-14 true] [-10 false] [1 false] [5 false] [-13 true]] 
tuples => [[8 false] [-1 false] [-14 true] [-10 false] [-8 true] [5 false] [-13 true]] 
tuples => [[8 false] [-1 false] [-14 true] [-10 false] [-8 true] [1 false] [-13 true]] 
tuples => [[8 false] [-1 false] [-14 true] [-10 false] [-8 true] [1 false] [5 false]] 
tuples => [[-14 true] [-10 false] [-8 true] [1 false] [5 false] [-13 true]] 
tuples => [[-1 false] [-10 false] [-8 true] [1 false] [5 false] [-13 true]] 
tuples => [[-1 false] [-14 true] [-8 true] [1 false] [5 false] [-13 true]] 
tuples => [[-1 false] [-14 true] [-10 false] [1 false] [5 false] [-13 true]] 
tuples => [[-1 false] [-14 true] [-10 false] [-8 true] [5 false] [-13 true]] 
tuples => [[-1 false] [-14 true] [-10 false] [-8 true] [1 false] [-13 true]] 
tuples => [[-1 false] [-14 true] [-10 false] [-8 true] [1 false] [5 false]] 
tuples => [[-10 false] [-8 true] [1 false] [5 false] [-13 true]] 
tuples => [[-14 true] [-8 true] [1 false] [5 false] [-13 true]] 
tuples => [[-14 true] [-10 false] [1 false] [5 false] [-13 true]] 
tuples => [[-14 true] [-10 false] [-8 true] [5 false] [-13 true]] 
tuples => [[-14 true] [-10 false] [-8 true] [1 false] [-13 true]] 
tuples => [[-14 true] [-10 false] [-8 true] [1 false] [5 false]] 
tuples => [[-8 true] [1 false] [5 false] [-13 true]] 
tuples => [[-10 false] [1 false] [5 false] [-13 true]] 
tuples => [[-10 false] [-8 true] [5 false] [-13 true]] 
tuples => [[-10 false] [-8 true] [1 false] [-13 true]] 
tuples => [[-10 false] [-8 true] [1 false] [5 false]] 
tuples => [[1 false] [5 false] [-13 true]] 
tuples => [[-8 true] [5 false] [-13 true]] 
tuples => [[-8 true] [1 false] [-13 true]] 
tuples => [[-8 true] [1 false] [5 false]] 
tuples => [[5 false] [-13 true]] 
tuples => [[-8 true] [-13 true]] 
tuples => [[-8 true] [5 false]] 
tuples => [[-13 true]] 
tuples => [[-8 true]] 
tuples => [[0 true] [-13 true]] 
tuples => [[-4 true] [-13 true]] 
tuples => [[-6 true] [-13 true]] 
tuples => [[-7 true] [-13 true]] 
tuples => [[-8 false] [-13 true]] 
tuples => [[-13 true]] 
tuples => [[-7 true]] 
tuples => [[0 true] [-13 true]] 
tuples => [[-4 true] [-13 true]] 
tuples => [[-6 true] [-13 true]] 
tuples => [[-7 false] [-13 true]] 
tuples => [[-7 true] [0 true]] 
tuples => [[-7 true] [-7 true]] 
tuples => [[-7 true] [-10 true]] 
tuples => [[-7 true] [-12 true]] 
tuples => [[-7 true] [-13 false]] 
{:result false, :seed 1511919758351, :failing-size 14, :num-tests 15, :fail [[[-7 false] [-14 false] [8 false] [-1 false] [-14 true] [-10 false] [-8 true] [1 false] [5 false] [-13 true]]], :shrunk {:total-nodes-visited 27, :depth 9, :result false, :smallest [[[-7 true] [-13 true]]]}, :test-var "dospec-line-46"} 

FAIL in (dospec-line-46) (clojure_test.cljc:21) 
expected: result 
    actual: false