How do I sample random subsequences in Clojure's test.check?

Question

I'm trying to generate a random solvable instance of the Subset Sum Problem. Wikipedia states that the target value should always be zero, but it's also possible to specify the target value, which is what I'm doing here.

So the idea is to create a random vector using (gen/vector gen/int) and then sample a random sub-vector and sum up that vector to create the target value. The problem with the obvious strategy using gen/elements is that it may sample the same element repeatedly.
My next best idea is to create a random set of indices and extract all the elements at those indices. Is there a simpler approach?

Answer 1

This code is a mock-up of what I think you are trying to do. It generates a vector of integers, each of which has a flag to indicate if it belongs in the subset (it could be none, some, or all). A dummy function (standin for subset-sum) decides if the test passes. You will need [tupelo "0.9.56"] in your project.clj.

(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)))

The above code generates output like this:

---------------------------------------
   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

Answer 2

This generator in test.chuck does what you're asking for by generating inclusion flags for each element.