Allocating array (list) algorithm permutations in python

So i'm having trouble to solve the following problem:

given an array size, lets say for the ease of the question size =20

it is filled with zeros as follows arr = [0]*20 ==> [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

we have couple of constant sample sizes, such as 4,3,2

SampleA=4, SampleB=3, SampleC= 2

i need to have the permutations/variations of how to allocate the list.

i can put each sample in different place/index

for example, sampleA= 4 i can put it in indexes of 0:3, or 1:4... 15:19.. (as you can see, there are quite a lot of possibilities)

the thing gets complicated once it get more crowded, for example:

3+2+3 +4

[0, x, x, x, 0, 0, x x, 0, x, x, x, 0, 0, 0, 0, x, x,x, x]

what i basically need, is to find all the possibilities to allocate samples,

i get a dictionary: key = sample size of indexes, and the value=many times it repeats.

for the upper example: {3:2,2:1,4:1}

and i would like the function to return a list of indexes !=0

for this example: [0, x, x, x, 0, 0, x x, 0, x, x, x, 0, 0, 0, 0, x, x,x, x]

the function will return: list_ind = [0,5,6,9,13,14,15,16]

1 answer

  • answered 2018-07-12 09:58 Danny Kaminski

    so i asked a colleague to help, and we came into a solution:

    i put an example of: 4:2, 3:1, 2:1

    or verbally:

    two times 4, one time 3, one time 2 the code below:

    *if someone can optimize, will be great

    size_of_wagon = 20
    dct = {4:2,3:1,2:1}
    l = [item for sublist in [[k] * v for (k, v) in dct.items()] for item in sublist]
    
    
    def gen_func(lstOfSamples, length, shift):
        try:
            # print(f'lstOfSamples={lstOfSamples}')
            sample = lstOfSamples[0]  # Take first sample
            for i in range(length - sample):
                for x in gen_func(lstOfSamples[1:], length - (sample + i), shift + sample + i):
                    yield [(shift + i, sample)] + x
        except:
            yield []
    
    
    g = list(gen_func(l, size_of_wagon, 0))
    
    for i in g:
        print(i)
    print(len(g))