Partitioning N-dimension array Creation

Question

Write Function to Generate N-array with some decimal place 

>>> func(2,3) # 2d-array with 3 dp, sum those value to 1
[0.001],[0.999] 
... 
[0.999],[0.001]
>>> func(3,3)
[0.001],[0.001],[0.998]
....
[0.998],[0.001],[0.001]

I can create those array with when using nested of for loop. When n> 4, creating such array is slow and hard.

You might do better creating constructor using `itertools`, since anything bigger than `n + d > 6` is going to risk memory problems regardless. — Daniel F, Jul 25 '17 at 08:00
My target is similar to the video https://www.youtube.com/watch?v=HdBX-Hn2uYo&feature=youtu.be How to split N coins to r people — Ken Ho, Jul 25 '17 at 08:25

Daniel F · Accepted Answer · 2017-08-01T11:57:29.267

With itertools you could do something like this:

import itertools as it
import numpy as np

def sum_generator(dim, dp, sum):
    i = np.linspace(0,1,10^dp)[1:-1].flat
    return it.ifilter(lambda x: np.sum(x)==sum, it.product(*(i,)*dim))

But it will still be very slow. You're ifilter-ing a lot (essentially the same constructor as a for loop, but done in c so still much faster)

What you're doing is called partitioning and there are some efficient algorithms for generators of such for integers, but they usually cover all n-dimensional spaces where n < sum. You can possibly adapt one to your purposes but I'm not good enough at recursive logic to create an effective generator.

score 0 · Answer 2 · answered Jul 25 '17 at 04:32

Hints

I would try using a recursive function

def auxiliary_function(dim, dp, sum):
   if sum < 0:
        raise Exception("error")
   if dim == 1:
        return [sum]
   val = random.random(1, sum * 10 ** dp - 1) / 10 ** dp
   aux_list = auxiliary_function(dim - 1, dp, sum - val)
   aux_list.append(val)
   return aux_list

And then I will call auxiliary_function(dim, dp, 1).

The goal of this auxiliary recursive function is to return a list of dim elements of precision dp whose sum is sum.

I let you adapt this function to return all the possible arrays you are looking for (mainly you have to replace the random generation of val by a loop between 0.001 (with the precision of dp) and sum.

Partitioning N-dimension array Creation

2 Answers2