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))

This works:

def cprod(x, c):
if c==1: return [[i] for i in x]
Sub= cprod(x, c-1)
return [i for F in x for i in [[F]+R for R in Sub]]

---------- Is there another (better) way to write [F]+R ???

it seems odd, compared to CONS in Lisp

Other ways to improve it?

On Tue, 21 May 2024 12:18:52 -0700
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))

This is cartesian power rather than arbitrary cartesian product. Here
is a Common Lisp version. It only works for vectors.

(defun cartesian-power
(vector power
&aux (len (length vector)) (wheels (make-array power :initial-element 0))
result (posres 0)
)
(when (or (eql power 0) (eql len 0))
(return-from cartesian-power (make-array 0)))
(setq result (make-array (expt len power)))
(do () (nil)
(setf (aref result posres)
(map 'vector (lambda (a) (aref vector a)) wheels))
(incf posres)
(let ((pos (position-if (lambda (a) (< a (1- len))) wheels)))
(unless pos (return-from cartesian-power result))
(incf (aref wheels pos))
(dotimes (i pos) (setf (aref wheels i) 0)))))

On 5/23/2024 8:46 AM, Spiros Bousbouras wrote:
> On Tue, 21 May 2024 12:18:52 -0700
> 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))
>
> This is cartesian power rather than arbitrary cartesian product. Here
> is a Common Lisp version. It only works for vectors.
>
> (defun cartesian-power
> (vector power
> &aux (len (length vector)) (wheels (make-array power :initial-element 0))
> result (posres 0)
> )
> (when (or (eql power 0) (eql len 0))
> (return-from cartesian-power (make-array 0)))
> (setq result (make-array (expt len power)))
> (do () (nil)
> (setf (aref result posres)
> (map 'vector (lambda (a) (aref vector a)) wheels))
> (incf posres)
> (let ((pos (position-if (lambda (a) (< a (1- len))) wheels)))
> (unless pos (return-from cartesian-power result))
> (incf (aref wheels pos))
> (dotimes (i pos) (setf (aref wheels i) 0)))))

Thanks!

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