[seqfan] Re: A general programming question involving recursion

[Fred Lunnon]

<< until only single element vectors remain >>

--- your example suggests that there is only one such vector:  [210] ?

  There are no repeated factors in your example, but you previously
stated that you take repeated factors into account.  In that case you
would need to generate permutations of a "bag" or "multiset", rather
than a just a set --- it is unclear from your description which scenario
you have in mind.

  I think what you mean is that you require to generate permutations
of bags comprising (products of) partitions of the bag of factors.
I can share a Maple procedure for bag permutations, which you may
be able to port to PARI reasonably easily; I hadn't encountered bag
partitions before, but I expect that they would prove no more difficult.

Fred Lunnon



On 4/25/18, 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
>>
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>