Finding repetitions of 8-tuples

Finding repetitions of 8-tuples

[Hans Lonsdale]

I have 16 collections of 8 numbers

(11 12 11 44 11 12 11 23)
(12 21 11 44 11 12 11 23)
and so on

I want to find whether there are repetitions of each 8-tuple.
The order in which the numbers occur is not important.

-- 
Sent with https://mailfence.com  
Secure and private email

Re: Finding repetitions of 8-tuples

[Arthur Miller]

Hans Lonsdale <hanslonsdale@mailfence.com> writes:

> I have 16 collections of 8 numbers
>
> (11 12 11 44 11 12 11 23)
> (12 21 11 44 11 12 11 23)
> and so on
>
> I want to find whether there are repetitions of each 8-tuple.
> The order in which the numbers occur is not important.

Have you looked at "lists as sets" chapter in the manual?

There is a 'cl-subsetp' you could start with:

  cl-subsetp is an autoloaded native-compiled Lisp function in ‘cl-seq.el’.

  (cl-subsetp LIST1 LIST2 [KEYWORD VALUE]...)

  Return true if LIST1 is a subset of LIST2.
  I.e., if every element of LIST1 also appears in LIST2.

  Keywords supported:  :test :test-not :key


(defvar l1 '(11 12 11 44 11 12 11 23))
(defvar l2 '(12 21 11 44 11 12 11 23))

(cl-subsetp l1 l2) ;; returns t

However there is a slight problem since it tests for the subset:

(defvar l3 '(12 21 11 44 11 12 11))

(cl-subsetp l3 l2) ;; returns t also

(and (cl-subsetp l3 l2)
     (= (length l3) (length l2))) ;; should do


Alternatively there functions to test membership, so you could easily roll your
own little defun with 'member' or something else.

Re: Finding repetitions of 8-tuples

[Ruijie Yu via Users list for the GNU Emacs text editor]

Arthur Miller <arthur.miller@live.com> writes:

> Hans Lonsdale <hanslonsdale@mailfence.com> writes:
>
>> I have 16 collections of 8 numbers
>>
>> (11 12 11 44 11 12 11 23)
>> (12 21 11 44 11 12 11 23)
>> and so on
>>
>> I want to find whether there are repetitions of each 8-tuple.
>> The order in which the numbers occur is not important.
>
> Have you looked at "lists as sets" chapter in the manual?
>
> There is a 'cl-subsetp' you could start with:
>
>   cl-subsetp is an autoloaded native-compiled Lisp function in ‘cl-seq.el’.
>
>   (cl-subsetp LIST1 LIST2 [KEYWORD VALUE]...)
>
>   Return true if LIST1 is a subset of LIST2.
>   I.e., if every element of LIST1 also appears in LIST2.
>
>   Keywords supported:  :test :test-not :key
>
>
> (defvar l1 '(11 12 11 44 11 12 11 23))
> (defvar l2 '(12 21 11 44 11 12 11 23))
>
> (cl-subsetp l1 l2) ;; returns t

I looked around and found out that `seq-set-equal-p' might be more
suitable for this task: this function performs a set-equality check
between the two lists (or, more broadly, sequences) whereas `cl-subsetp'
checks for subsets, as you have noted later in your message.

> [...]

Best,


RY

Re: Finding repetitions of 8-tuples

[Yuri Khan]

On Sun, 1 Jan 2023 at 22:19, Arthur Miller <arthur.miller@live.com> wrote:

> > I have 16 collections of 8 numbers
> >
> > (11 12 11 44 11 12 11 23)
> > (12 21 11 44 11 12 11 23)
> > and so on
> >
> > I want to find whether there are repetitions of each 8-tuple.
> > The order in which the numbers occur is not important.
>
> Have you looked at "lists as sets" chapter in the manual?

This line of thought leads nowhere because treating a list as a set
ignores its duplicate counts. I take it that in the OP’s problem
statement (1 1 1 1 1 2 2 2) is to be considered distinct from (1 1 1 1
2 2 2 2), but, treated as sets, they are both equivalent to (1 2). The
original problem calls for multisets — containers where the order is
not significant but the counts of duplicates are.

Sorting each list and comparing the result of sorting, as suggested in
another reply, is going to be a better approach.

Alternatively, one might hash each element and xor the hashes
together. However, this carries collision risk inherent in hash-based
solutions — if hashes are different, the multisets are different, but
if the hashes are equal, this does not guarantee the equality of
multisets.

Re: Finding repetitions of 8-tuples

[Hans Lonsdale]

> ----------------------------------------
> From: Yuri Khan <yuri.v.khan@gmail.com>
> Sent: Sun Jan 01 17:39:36 CET 2023
> To: Arthur Miller <arthur.miller@live.com>
> Cc: Hans Lonsdale <hanslonsdale@mailfence.com>, Help Gnu Emacs <help-gnu-emacs@gnu.org>
> Subject: Re: Finding repetitions of 8-tuples
> 
> 
> On Sun, 1 Jan 2023 at 22:19, Arthur Miller <arthur.miller@live.com> wrote:
> 
> > > I have 16 collections of 8 numbers
> > >
> > > (11 12 11 44 11 12 11 23)
> > > (12 21 11 44 11 12 11 23)
> > > and so on
> > >
> > > I want to find whether there are repetitions of each 8-tuple.
> > > The order in which the numbers occur is not important.
> >
> > Have you looked at "lists as sets" chapter in the manual?
> 
> This line of thought leads nowhere because treating a list as a set
> ignores its duplicate counts. I take it that in the OP’s problem
> statement (1 1 1 1 1 2 2 2) is to be considered distinct from (1 1 1 1
> 2 2 2 2), but, treated as sets, they are both equivalent to (1 2). The
> original problem calls for multisets — containers where the order is
> not significant but the counts of duplicates are.

That's correct.
 
> Sorting each list and comparing the result of sorting, as suggested in
> another reply, is going to be a better approach.

Agreed
 
> Alternatively, one might hash each element and xor the hashes
> together. However, this carries collision risk inherent in hash-based
> solutions — if hashes are different, the multisets are different, but
> if the hashes are equal, this does not guarantee the equality of
> multisets.
> 


-- 
Sent with https://mailfence.com  
Secure and private email

Re: Finding repetitions of 8-tuples

[Ruijie Yu via Users list for the GNU Emacs text editor]

Hans Lonsdale <hanslonsdale@mailfence.com> writes:

> I have 16 collections of 8 numbers
>
> (11 12 11 44 11 12 11 23)
> (12 21 11 44 11 12 11 23)
> and so on
>
> I want to find whether there are repetitions of each 8-tuple.
> The order in which the numbers occur is not important.

I think your best bet is to sort each 8-tuple and compare the sorted
lists afterwards.  Can't think of anything better at the moment.

Best,


RY

Re: Finding repetitions of 8-tuples

[Hans Lonsdale]

> ----------------------------------------
> From: Ruijie Yu via Users list for the GNU Emacs text editor <help-gnu-emacs@gnu.org>
> Sent: Sun Jan 01 16:16:35 CET 2023
> To: Hans Lonsdale <hanslonsdale@mailfence.com>
> Cc: <help-gnu-emacs@gnu.org>
> Subject: Re: Finding repetitions of 8-tuples
> 
> 
> 
> Hans Lonsdale <hanslonsdale@mailfence.com> writes:
> 
> > I have 16 collections of 8 numbers
> >
> > (11 12 11 44 11 12 11 23)
> > (12 21 11 44 11 12 11 23)
> > and so on
> >
> > I want to find whether there are repetitions of each 8-tuple.
> > The order in which the numbers occur is not important.
> 
> I think your best bet is to sort each 8-tuple and compare the sorted
> lists afterwards.  Can't think of anything better at the moment.
> 
> Best,
> RY

Sorting is a very good idea for an suitable algorithm. 


-- 
Sent with https://mailfence.com  
Secure and private email

Re: Finding repetitions of 8-tuples

[Emanuel Berg]

Hans Lonsdale wrote:

> I have 16 collections of 8 numbers
>
> (11 12 11 44 11 12 11 23)
> (12 21 11 44 11 12 11 23)
> and so on
>
> I want to find whether there are repetitions of each
> 8-tuple. The order in which the numbers occur is
> not important.

(require 'cl-lib)

(let ((sl '( (11 12 11 44 11 12 11 23)
             (12 21 11 44 11 12 11 23)
             (12 21 11 44 11 12 11 23)
             ;; etc
             )))
  (cl-delete-duplicates
    (mapcar (lambda (s) (sort s #'<)) sl)
    :test #'equal) )

-- 
underground experts united
https://dataswamp.org/~incal