Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Re: [mg5065] List help needed
Replies: 0

 John Fultz Posts: 736 Registered: 12/7/04
Re: [mg5065] List help needed
Posted: Oct 30, 1996 12:19 AM

Here's one solution to your problem. In order to define this function
properly, you must load DiscreteMath`Combinatorica`, as I've done here.
This package needs to be loaded for the function Partitions[], which does
exactly what you want to do with integers instead of subsets. The rest
of the function essentially maps the result of Partitions[] (and all its
permutations) onto your base set to form the appropriate subsets. Usage
is:

SubSetPartitions[l, n]

where l is your list and n is the number of parts you want to break your
list into. For your particular example of a list of size 20 and n == 10, it
will take quite long to run (if you're not on a real zippy machine, go eat
lunch or something while it runs). Also, the size of the output will be
tremendous, and displaying it in the front end will incur a lot of overhead
in formatting, sending the expression to the front end, and so on...if you
don't need to see the result, then make sure you suppress the output or
you'll incur a much greater time and memory overhead.

Also, this function is not completely generalized in the sense that it
doesn't take into account the boundary conditions where n==1 || n==Length[l].
I assumed this information was useless to you anyway, so didn't bother, but
these conditions could be programmed in.

Hope this helps!

Sincerely,

John Fultz
jfultz@wolfram.com
Front End Group
Wolfram Research, Inc.

Needs["DiscreteMath`Combinatorica`"]

SubSetPartitions[mylist_, numparts_Integer] :=
Flatten[Module[{mylistlength, mylisttable, mypartitionstable, PartitionToSubsets},
mylistlength = Length[mylist];
mylisttable = Map[Drop[mylist, #]&, Range[0, Length[mylist]]];
mypartitionstable = Select[Partitions[mylistlength],
Length[#] == numparts &];
PartitionToSubsets[parray_] :=
Module[{cumarray = FoldList[Plus, 1, Drop[parray, -1]]},
{cumarray, parray}]];
Map[Map[PartitionToSubsets, Permutations[#]]&,
mypartitionstable]], 1] /. {{x_}:>x}

> Hi,
>
> I need a little help with lists. What I would like to do is the
> following:
>
> N by combining adjacent elements of the original list into sub lists.
> This might become clearer with an example.
>
> Given {a,b,c,d,e} of length 5, ALL possible length 4 lists subject to
> the conditions above are:
>
> {{a,b},c,d,e}, {a,{b,c},d,e}, {a,b,{c,d},e} and {a,b,c,{d,e}}
>
> two of the possible length 3 lists are
>
> {a,{b,c,d},e} and {{a,b},c,{d,e}}
>
> I hope you get the picture.
>
> In the "real" problem, N would be around 20 and n would be around 10.
>
>
>
> John
> jrowney@arco.com
>