Sujet : Re: Cprod (Cartesian Product) in Lisp (or Scheme)
De : 643-408-1753 (at) *nospam* kylheku.com (Kaz Kylheku)
Groupes : comp.lang.lisp comp.lang.schemeDate : 24. May 2024, 04:00:11
Autres entêtes
Organisation : A noiseless patient Spider
Message-ID : <20240523183817.334@kylheku.com>
References : 1
User-Agent : slrn/pre1.0.4-9 (Linux)
On 2024-05-21, HenHanna <
HenHanna@devnull.tb> wrote:
>
>
How would you write this in Lisp (or Scheme) ?
>
>
>
in Python... (writing this out: itertools.product([0, 1], repeat=N )
>
The value can be a list or a Tuple.
>
cprod([0, 1], 1) => ((0) (1))
>
cprod([0, 1], 2) => ((0,0) (0,1) (1,0) (1,1))
Another name for this is "repeating permutations": permutations
of the (0 1) elements, such that repetitions are allowed.
How I would write this is by having it built into the language.
This is the TXR Lisp interactive listener of TXR 294.
Quit with :quit or Ctrl-D on an empty line. Ctrl-X ? for cheatsheet.
Everything you type here can and will be used against you in
comp.lang.lisp.
1> (rperm '(0 1) 2)
((0 0) (0 1) (1 0) (1 1))
I would have it as a lazy list, so we can ask for the first 5
items of an incredibly long instance of such a sequence.
2> (take 5 (rperm #\A..#\Z 15))
((#\A #\A #\A #\A #\A #\A #\A #\A #\A #\A #\A #\A #\A #\A #\A)
(#\A #\A #\A #\A #\A #\A #\A #\A #\A #\A #\A #\A #\A #\A #\B)
(#\A #\A #\A #\A #\A #\A #\A #\A #\A #\A #\A #\A #\A #\A #\C)
(#\A #\A #\A #\A #\A #\A #\A #\A #\A #\A #\A #\A #\A #\A #\D)
(#\A #\A #\A #\A #\A #\A #\A #\A #\A #\A #\A #\A #\A #\A #\E))
3> (take 5 (rperm (join #\A..#\Z) 15))
("AAAAAAAAAAAAAAA" "AAAAAAAAAAAAAAB" "AAAAAAAAAAAAAAC" "AAAAAAAAAAAAAAD"
"AAAAAAAAAAAAAAE")
That reminds me; I should probably implement iterators which
step over these sequences, to complement the lazy list implementation.
The implementation of rperm starts here:
https://www.kylheku.com/cgit/txr/tree/combi.c?h=txr-294#n264The heart of it is the rperm_gen_fun function, which updates
a permutation vector to the next permutation.
The state consists of a vector of lists, and a reset list.
For instance, if we are generating triplets of (A B C D), the
vector gets initialized to a copy of the list in every position:
#((A B C D)
(A B C D)
(A B C D))
We take the first repeating permutation by taking the car
of every list: (A A A A). Then to generate the next permutation,
we pop the last list:
#((A B C D)
(A B C D)
(B C D)) ;; pop!
When we pop the last list empty, we restore it back to (A B C D),
and pop the next one:
#((A B C D)
(A B C D)
(B))
#((A B C D)
(A B C D)
()) ;; pop! oops!
#((A B C D)
(B C D) ;; pop!
(A B C D)) ;; whump! (restored)
When we pop the first list down to nil, then we are done.
The rperm_while_fun tests for this condition.
It's a very simple algorithm compared to the nonrepeating
permutations, and repeating or nonrepeating combinations.
-- TXR Programming Language: http://nongnu.org/txrCygnal: Cygwin Native Application Library: http://kylheku.com/cygnalMastodon: @Kazinator@mstdn.ca