• Top
  • Documentation
  • Books
  • Recursion-and-induction
  • Boolean-reasoning
  • Projects
    • Apt
    • Acre
    • Milawa
    • Smtlink
    • Abnf
    • Vwsim
    • Isar
    • Wp-gen
    • Dimacs-reader
    • Legacy-defrstobj
    • Prime-field-constraint-systems
    • Proof-checker-array
    • Soft
    • Rp-rewriter
    • Farray
    • 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
    • Taspi
    • Bitcoin
    • Des
    • Ethereum
    • Sha-2
    • Yul
    • Zcash
    • Proof-checker-itp13
    • Bigmem
    • Regex
    • ACL2-programming-language
    • Java
    • C
    • Jfkr
    • X86isa
    • Equational
    • Cryptography
    • Where-do-i-place-my-book
    • Json
    • Built-ins
    • Execloader
    • Solidity
    • Paco
    • Concurrent-programs
  • Debugging
  • Std
  • Proof-automation
  • Macro-libraries
  • ACL2
  • Interfacing-tools
  • Hardware-verification
  • Software-verification
  • Testing-utilities
  • Math

• 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