[seqfan] Re: A general programming question involving recursion

[Joe Slater]

If I understand you correctly you want a function f on a vector v,
returning another vector that comprises the products of the power set of v
(excluding the empty set). If so, perhaps this is what you want:
f(v)=vecsort(vector(2^#v-1,y,factorback(vector(2^#v-1,x,vecextract(v,x))[y])),,8)

? f([3,3,5,7])
%1 = [3, 5, 7, 9, 15, 21, 35, 45, 63, 105, 315]

It shouldn't be hard to amend this if you don't want the prime elements
(e.g., 3,5,7) included. This function only returns unique products - if you
want to keep duplicates then get rid of the vecsort(,,8) wrapper.

Cheers,
Joe

On Thu, Apr 26, 2018 at 7:43 AM, Felix Fröhlich <felix.froe at gmail.com>
wrote:

> Dear SeqFans,
>
> I am trying to write a somewhat complex PARI program for a sequence I am
> preparing. While preparing that program, I have run into a general
> algorithmic problem. Without going into detail about why I need to perform
> those operations, let me describe what I am trying to do:
>
> I take a number n and compute the list of prime factors with repetition.
> Now, from that list of prime factors I want to compute recursively all
> possible permutations of all sets of numbers that can be obtained by
> multiplying two prime factors in the list. In this way I want to obtain ALL
> possible products from multplying any two prime factors from the original
> set and from all permutations of that set and, recursively, all products
> from all permutations resulting from multiplying two factors until the
> products result in single numbers.
>
> Normally, I would do this using two nested loops, one for going through the
> permutations and one for going through the multiply over each vector. But
> then, I also need to go through the permutations of the resulting vector
> with multiplied elements and through the vectors resulting from multiplying
> two neighboring elements of those vectors permutations, ..., and so on.
>
> How is this best done in order to obtain all different permutations from
> all vectors from multiplying two neighboring vector elements, starting with
> a vector of any length down to a single element?
>
> Ideas anyone?
>
> Best regards
>
> Felix
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>