• Top
  • Documentation
  • Books
  • Boolean-reasoning
  • Projects
    • Apt
    • Acre
    • Milawa
    • Smtlink
    • Aleobft
    • Abnf
    • Vwsim
    • Isar
    • Wp-gen
    • Dimacs-reader
    • Pfcs
    • Legacy-defrstobj
    • Proof-checker-array
    • Soft
    • Farray
    • Rp-rewriter
    • Instant-runoff-voting
      • Fairness-criteria
      • Candidate-with-least-nth-place-votes
      • Eliminate-candidate
      • First-choice-of-majority-p
      • Candidate-ids
        • Sorting-candidate-ids
      • Irv
      • Create-nth-choice-count-alist
      • Irv-alt
      • Irv-ballot-p
      • Majority
      • Number-of-candidates
      • List-elements-equal
      • Number-of-voters
    • Imp-language
    • Sidekick
    • Leftist-trees
    • C
    • Java
    • Taspi
    • Bitcoin
    • Des
    • Ethereum
    • X86isa
    • Sha-2
    • Yul
    • Riscv
    • Zcash
    • Proof-checker-itp13
    • Regex
    • ACL2-programming-language
    • Json
    • Jfkr
    • Equational
    • Cryptography
    • Poseidon
    • Where-do-i-place-my-book
    • Bigmems
    • Builtins
    • Axe
    • Execloader
    • Solidity
    • Leo
    • Paco
    • Concurrent-programs
  • Debugging
  • Std
  • Proof-automation
  • Macro-libraries
  • ACL2
  • Interfacing-tools
  • Hardware-verification
  • Software-verification
  • Math
  • Testing-utilities

• Instant-runoff-voting

Candidate-ids

Get a sorted list of candidate IDs currently in the election

Signature

(candidate-ids xs) → cids

Arguments

xs — Guard (irv-ballot-p xs).

Returns

cids — Type (true-listp cids).

Definitions and Theorems

Function: candidate-ids

(defun candidate-ids (xs)
  (declare (xargs :guard (irv-ballot-p xs)))
  (let ((__function__ 'candidate-ids))
    (declare (ignorable __function__))
    (acl2::<-sort (remove-duplicates-equal (acl2::flatten xs)))))

Theorem: true-listp-of-candidate-ids

(defthm true-listp-of-candidate-ids
  (b* ((cids (candidate-ids xs)))
    (true-listp cids))
  :rule-classes :type-prescription)

Theorem: nat-listp-of-candidate-ids

(defthm nat-listp-of-candidate-ids
  (implies (irv-ballot-p xs)
           (nat-listp (candidate-ids xs))))

Theorem: consp-of-candidate-ids

(defthm consp-of-candidate-ids
  (implies (and (non-empty-true-list-listp xs)
                (consp xs))
           (consp (candidate-ids xs)))
  :rule-classes :type-prescription)

Theorem: subset-of-candidate-ids-cdr

(defthm subset-of-candidate-ids-cdr
  (subsetp-equal (candidate-ids (cdr xs))
                 (candidate-ids xs)))

Theorem: nat-listp-and-subsetp-equal

(defthm nat-listp-and-subsetp-equal
  (implies (and (subsetp-equal x y)
                (true-listp x)
                (nat-listp y))
           (nat-listp x)))

Theorem: nat-listp-and-set-equiv

(defthm nat-listp-and-set-equiv
  (implies (and (acl2::set-equiv x y)
                (true-listp x)
                (true-listp y))
           (iff (nat-listp x) (nat-listp y))))

Theorem: duplicity-of-element-in-no-duplicatesp-list

(defthm duplicity-of-element-in-no-duplicatesp-list
  (implies (and (member-equal e x)
                (no-duplicatesp-equal x))
           (equal (acl2::duplicity e x) 1)))

Theorem: cdr-no-duplicatesp-equal

(defthm cdr-no-duplicatesp-equal
  (implies (no-duplicatesp-equal xs)
           (no-duplicatesp-equal (cdr xs))))

Theorem: no-duplicatesp-equal-of-remove-equal

(defthm no-duplicatesp-equal-of-remove-equal
  (implies (no-duplicatesp-equal x)
           (no-duplicatesp-equal (remove-equal id x))))

Theorem: remove-equal-car-lst-no-duplicatesp-equal

(defthm remove-equal-car-lst-no-duplicatesp-equal
  (implies (and (no-duplicatesp-equal lst)
                (true-listp lst))
           (equal (remove-equal (car lst) (cdr lst))
                  (cdr lst))))

Theorem: subset-member-remove-equal-lemma

(defthm subset-member-remove-equal-lemma
  (implies (and (subsetp-equal y (cons e x))
                (member-equal e y))
           (subsetp-equal (remove-equal e y) x)))

Theorem: equal-len-of-no-duplicates-set-equivs

(defthm equal-len-of-no-duplicates-set-equivs
  (implies (and (acl2::set-equiv x y)
                (no-duplicatesp-equal x)
                (no-duplicatesp-equal y))
           (equal (len x) (len y))))

Theorem: candidate-ids-nat-listp-smaller

(defthm candidate-ids-nat-listp-smaller
  (implies (nat-listp (candidate-ids xs))
           (nat-listp (candidate-ids (cdr xs)))))

Theorem: subset-of-flatten

(defthm subset-of-flatten
  (implies (subsetp-equal ys xs)
           (subsetp-equal (acl2::flatten ys)
                          (acl2::flatten xs))))

Theorem: subsetp-of-irv-ballots-implies-subsetp-of-candidate-ids

(defthm subsetp-of-irv-ballots-implies-subsetp-of-candidate-ids
  (implies (subsetp-equal ys xs)
           (subsetp-equal (candidate-ids ys)
                          (candidate-ids xs))))

Theorem: no-duplicates-in-candidate-ids

(defthm no-duplicates-in-candidate-ids
  (no-duplicatesp-equal (candidate-ids xs)))

Subtopics

Sorting-candidate-ids