Deutsch English Français Italiano |
<20240523183817.334@kylheku.com> View for Bookmarking (what is this?) Look up another Usenet article |
Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: Kaz Kylheku <643-408-1753@kylheku.com> Newsgroups: comp.lang.lisp,comp.lang.scheme Subject: Re: Cprod (Cartesian Product) in Lisp (or Scheme) Date: Fri, 24 May 2024 02:00:11 -0000 (UTC) Organization: A noiseless patient Spider Lines: 92 Message-ID: <20240523183817.334@kylheku.com> References: <v2is2s$ndjr$4@dont-email.me> Injection-Date: Fri, 24 May 2024 04:00:11 +0200 (CEST) Injection-Info: dont-email.me; posting-host="e11ec59bf0ae08b37203ccb330e57e74"; logging-data="2252792"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19Ip0/PohK1xumwOkjHJVT4exsc1Jd/xeY=" User-Agent: slrn/pre1.0.4-9 (Linux) Cancel-Lock: sha1:LcFAy3HNgI8SJi2TyLRL5uoZx+o= Bytes: 3732 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#n264 The 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/txr Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal Mastodon: @Kazinator@mstdn.ca