[seqfan] Re: A general programming question involving recursion
M. F. Hasler
oeis at hasler.fr
Thu Apr 26 02:23:31 CEST 2018
Felix,
I think you don't need to consider permutations,
just replace any couple v[i], v[j] , 1 <= i < j <= #v by its product.
You can do this using
forvec(i=vector(2,i,[1,#v]), new=v[^i[2]]; new[i[1]]*= v[i[2]] , ..., 2)
For repeated prime factors, you can do some additional tweaks for
efficiency...
- Maximilian
On Wed, Apr 25, 2018 at 5:56 PM, Felix Fröhlich <felix.froe at gmail.com>
wrote:
> A small clarification to the above:
>
> If I have a vector like [2, 3, 5, 7], then I need all permutations like [2,
> 3, 7, 5], [2, 5, 3, 7], etc. I have working code for that part. Then I need
> all vectors like [6, 5, 7], [2, 15, 7], [2, 3, 35] and [10, 3, 7], [2, 15,
> 7], [2, 5, 21] and again all permutations of each of those vectors, i.e.,
> [6, 5, 7], [5, 6, 7], [6, 7, 5], [5, 7, 6], [7, 5, 6], [7, 6, 5] and again
> all vectors from multiplying any two elements of those vectors: [30, 7],
> [6, 35], [42, 5], [35, 6], etc and all permutations of those vectors until
> only single element vectors remain.
>
> Felix
>
> 2018-04-25 23:43 GMT+02:00 Felix Fröhlich <felix.froe at gmail.com>:
>
> > 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
>
More information about the SeqFan
mailing list