Re: Simple n-tuple problem - with no simple solution
- To: mathgroup at smc.vnet.net
- Subject: [mg115845] Re: Simple n-tuple problem - with no simple solution
- From: DrMajorBob <btreat1 at austin.rr.com>
- Date: Sat, 22 Jan 2011 03:23:57 -0500 (EST)
I didn't think rearrangements of a solution mattered, so my approach was
different... and I found that Solve is pretty darn fast!
My approach also allows Range[0,1,.05] to be replaced with almost any list
of reals, though I didn't experiment with that.
Here are some timings.
n = 5; addends = Rationalize@Range[0, 1.0, 0.05];
Clear[t1]
t1[range_List, n_Integer] :=
Module[{addends = Rationalize@range, multipliers, m, sum, nonNegative},
multipliers = Array[m, Length@range];
sum = Total@multipliers;
nonNegative = And @@ Thread[multipliers >= 0];
Sort[multipliers /.
Solve[{multipliers.addends == 1, nonNegative, sum == n}, multipliers,
Integers]]]
Length@t1[addends, n] // Timing
{1.44372, 192}
"Sseziwa Mukasa" < mukasa at jeol.com >
{First@Timing[
sm = Flatten[
Outer[If[Plus[##] == 1, {##}, Sequence @@ {}] &,
Sequence @@ Table[addends, {n}]], n - 1];], Length@Union[Sort /@
sm]}
{23.6318, 192}
Daniel Lichtblau:
getSolutions[sum_, max_, 1] := If[max < sum, {}, {{sum}}]
getSolutions[sum_, max_, n_] :=
Module[{subsols}, Union[Flatten[Table[subsols = getSolutions[j, max, n -
1];
If[Length[subsols] >= 1,
Table[Insert[subsols[[i]], sum - j, k], {k, 1, n}, {i,
Length[subsols]}], {}], {j, Max[sum - max, 0], sum}], 2]]]
{First@Timing[dl = getSolutions[20, 20, n];], dl = Union[Sort /@ dl];
Length@Union[Sort /@ dl], Total /@ dl // Union}
{0.538832, 192, {20}}
Bob Hanlon:
Needs["Combinatorica`"] // Quiet
{First@Timing[bh = Compositions[20, n]/20;], Length@Union[Sort /@ bh],
Total /@ bh // Union}
{0.167242, 192, {1}}
Bob looks very good, and Sseziwa seems out of the running.
Next for n = 7:
n = 7;
Length@t1[addends, n] // Timing
{1.85135, 364}
{First@Timing[dl = getSolutions[20, 20, n];], dl = Union[Sort /@ dl];
Length@Union[Sort /@ dl]}
{21.6415, 364}
{First@Timing[bh = Compositions[20, n]/20;], Length@Union[Sort /@ bh]}
{1.79257, 364}
Daniel seems out of the running.
For n = 9:
n = 9;
Length@t1[addends, n] // Timing
{2.04216, 488}
{First@Timing[bh = Compositions[20, n]/20;], Length@Union[Sort /@ bh]}
{29.1514, 488}
The Compositions method rendered Mathematica unresponsive at n = 10, but
here's n = 25 for my approach:
n = 25;
Length@t1[addends, n] // Timing
{2.57619, 627}
I'd say Solve (which must use Integer Linear Programming for this) is the
way to go.
Bobby
On Fri, 21 Jan 2011 03:35:46 -0600, Bob Hanlon <hanlonr at cox.net> wrote:
>
> Load Combinatorica then use 0.05 * Compositions[20, n]
>
> Needs["Combinatorica`"] // Quiet
>
> n = 5;
>
> Timing[c1 = Select[Tuples[Table[Range[0, 1.0, .05], {n}]], Total[#] == 1
> &];]
>
> {14.4972, Null}
>
> Timing[c2 = 0.05 Compositions[20, n];]
>
> {0.044528, Null}
>
> c1 == c2
>
> True
>
>
> Bob Hanlon
>
> ---- Don <donabc at comcast.net> wrote:
>
> =============
> Problem: Given an n-tuple (n >= 1). with each element able to take
> on the values in
> Range[0, 1.0, .05] , produce all the n-tuples that sum to 1.0.
>
> The most direct way to solve this problem is to generaate all possible
> n-tuples and Select out all those that sum to 1.0.
>
> For example, when n = 2 :
>
> n = 2;
> Select[Tuples[Table[Range[0, 1.0, .05], {n}]], Total[#] == 1 &]
>
> The problem with this solution is that the number of n-tuples that are
> generated before the Select is used grows exponentially fast as a
> function
> of n - causing the system to run out of memory (RAM) very quickly.
>
> Is there a more memory efficient way to solve this problem that
> doesn't
> use so much memory but still is not too slow in terms of processor
> time?
>
> Thank you.
>
>
>
--
DrMajorBob at yahoo.com