[seqfan] Re: A general programming question involving recursion

[hv at crypt.org]

Of course this also requires d > 1, either from a suitably tailored
divisors() function or with an additional check.

Hugo

Earlier, I wrote:
:If I correctly understand the requirement, you want V(n), the set of vectors
:consisting of:
:- the single empty vector [] if n = 1
:- else for each d that divides n, the set of vectors consisting of d
:  concatenated with each vector in V(n/d)
:
:I'm no PARI expert; in Perl you could write that something like:
:
:sub V {
:    my($n) = @_;
:    return [] if $n == 1;
:    return map {
:        my $d = $_;
:        map [ $d, @$_ ], V($n / $d);
:    } divisors($n);
:}
:
:Hugo
:=?UTF-8?Q?Felix_Fr=C3=B6hlich?= <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
::>
::
::--
::Seqfan Mailing list - http://list.seqfan.eu/