MathGroup Archive 2001

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: [Q] Generalized Partitions

  • To: mathgroup at smc.vnet.net
  • Subject: [mg29993] Re: [mg29942] [Q] Generalized Partitions
  • From: Andrzej Kozlowski <andrzej at tuins.ac.jp>
  • Date: Sat, 21 Jul 2001 00:49:01 -0400 (EDT)
  • Sender: owner-wri-mathgroup at wolfram.com

Since your problem involves rather large numbers none of the methods I have
suggested so far will work. Both of them build up unnecessarily long lists.
The method to use is known as backtracking. The most efficient way would be
to write your own backtracking program. However, one can also rely on the
already existing "general" one in the Combinatorica package. In your case it
will take a very long time (you need a fast computer and be ready to wait).

To speed up thecomputations it would be a good idea to be able to Compile
the Backtrack function. I have not quite been able to do this so far (I
would need to think about it more, as there seem to be some difficulties and
I have little experience with compiling functions) but I have complied a one
component of the function (the Solution function below) which results in a
speed up of 55%. Compiling the entire function should result in additional
gains.

Here is the code of the Backtrack function taken form the Combinatorica
package and modified to use Compile:

In[1]:=
Backtrack[space_List,partialQ_,solutionQ_,flag_:One] :=
    Module[{n=Length[space],all={},done,index,v=2,solution},
        index=Prepend[ Table[0,{n-1}],1];
        While[v > 0,
            done = False;
            While[!done && (index[[v]] < Length[space[[v]]]),
                index[[v]]++;
                done = Apply[partialQ,{Solution[space,index,v]}];
            ];
            If [done, v++, index[[v--]]=0 ];
            If [v > n,
                solution = Solution[space,index,n];
                If [Apply[solutionQ,{solution}],
                    If [SameQ[flag,All],
                        AppendTo[all,solution],
                        all = solution; v=0
                    ]
                ];
                v--
            ]
        ];
        all
    ];

In[2]:=
Solution=Compile[{{space,_Integer,2},{index,_Integer,1},{count,_Integer}},
    Module[{i}, Table[space[[ i,index[[i]] ]], {i,count}] ]]

Now we set up the auxiliary functions for our problem and the problem
itself. I shall much smaller data than you want to use. This much smaller
example below is pretty fast:

In[3]:=
l={1,4,7,10,13,16,19,22,25,28,31,34,37,40,43,47,50,53,56,59};
In[4]:=
k=6;
In[5]:=
n=51;

In other words, we shall try to find the partitions of 51 as a sum of 6
members of the list l.

Next we define the solution space for our problem, the test for a partial
solution (a potential solution is rejected if it fails the test) and the
test for the final solution.

In[6]:=
sp = Table[l, {k}];

In[7]:=
partialQ[l_, n_] := Tr[l] + (k - Length[l])*Min[l] <= n &&
   Tr[l] + (k - Length[l])*Max[l] >= n

In[8]:=
solutionQ[l_, n_] := Tr[l] == n


Now we can run our program:

In[9]:=
Length[Backtrack[sp,partialQ[#,n]&,solutionQ[#,n]&,All]]//Timing
Out[9]=
{10.4333 Second,1386}

This was done on a 400 MHZ Macintosh. The problem is certainly of high time
complexity so for your size of data I would expect a very long wait.


-- 
Andrzej Kozlowski
Toyama International University
JAPAN

http://platon.c.u-tokyo.ac.jp/andrzej/



on 01.7.19 11:43 PM, Janusz Kawczak at jkawczak at uncc.edu wrote:

> Dear Andrzej:
> 
> thank you for your e-mail. Indeed, your solution seems to do the job, but
> for a quite small data. I am trying to get the following partition into an
> ordered sets and I am interested ONLY in the cardinality of the set. Here
> is the magnitude of one of my problems:
> 
> l={1, 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 34, 37, 40, 43, 47, 50, 53,
> 56, 59, 62, 65, 68, 71, 74, 77, 80, 83, 86, 89, 92, 95, 98, 101, 104, 107,
> 110, 113, 116, 119, 122, 125, 128, 131, 134, 138, 142, 146, 150, 155, 160,
> 165, 170,
> 175}
> 
> The numbers to be partinioned are at least 2500 and they are composed of
> 18 elements. When I tried your function I got an error message that the
> number of iterations (256) has be exceeded, i.e. in you function
> 
> Length[OrderedPartitions[2500, 18, l]]
> 
> Any suggestions?
> 
> Dziekuje za pomoc.
> Janusz.
> 
> ** Janusz Kawczak                            **
> ** UNC at Charlotte, Department of Mathematics, Room 350F        **
> ** 9201 University City Blvd.                        **
> ** Charlotte, NC, 28223-0001, U.S.A.                    **
> ** Tel.: (704) 687-2566 (W) (704) 921-0273 (H) Fax.: (704) 687-6415    **
> 
> On Thu, 19 Jul 2001, Andrzej Kozlowski wrote:
> 
> andrze>You do not state if the partitions should be into ordered or un-ordered
> andrze>sets. Anyway, probably the easiest way is to make use of the standard
> andrze>package Combinatorica:
> andrze>
> andrze>In[1]:=
> andrze><<DiscreteMath`Combinatorica`
> andrze>
> andrze>In[2]:=
> andrze>OrderedPartitions[n_, k_, l_List] :=
> andrze>  Select[Compositions[n, k], Complement[#1, l] == {}& ]
> andrze>
> andrze>In[3]:=
> andrze>UnorderedPartitions[n_, k_, l_List] :=
> andrze>  Select[OrderedPartitions[n, k, l], OrderedQ]
> andrze>
> andrze>Using your list:
> andrze>
> andrze>In[4]:=
> andrze>l={1,3,4,5,6,7,9};
> andrze>
> andrze>In[5]:=
> andrze>OrderedPartitions[10,2,l]
> andrze>Out[5]=
> andrze>{{1,9},{3,7},{4,6},{5,5},{6,4},{7,3},{9,1}}
> andrze>In[6]:=
> andrze>UnorderedPartitions[10,2,l]
> andrze>Out[6]=
> andrze>{{1,9},{3,7},{4,6},{5,5}}
> andrze>
> andrze>--
> andrze>Andrzej Kozlowski
> andrze>Toyama International University
> andrze>JAPAN
> andrze>
> andrze>http://platon.c.u-tokyo.ac.jp/andrzej/
> andrze>http://sigma.tuins.ac.jp/~andrzej/
> 
> 



  • Prev by Date: Re: [Q] Generalized Partitions
  • Next by Date: Re: [Q] Generalized Partitions
  • Previous by thread: Re: [Q] Generalized Partitions
  • Next by thread: Re: [Q] Generalized Partitions