[seqfan] Re: A general programming question involving recursion

[hv at crypt.org]

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/