CODEWITHSUNDEEP
pythonnumpy
Ken Ho
Ken Ho

Reputation: 480

Partitioning N-dimension array Creation

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.

Upvotes: 0

Views: 70

Answers (2)

Daniel F
Daniel F

Reputation: 14399

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.

Upvotes: 1

fonfonx
fonfonx

Reputation: 1465

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.

Upvotes: 0

Related Questions